For a simple graph G with n-vertices, m edges and having Laplacian eigenvalues μ1,μ2,…,μn−1,μn=0, let Sk(G)=∑i=1kμi, be the sum of k largest Laplacian eigenvalues of G. Brouwer conjectured that ...Sk(G)≤m+(k+12), for all k=1,2,…,n. We obtain upper bounds for Sk(G) in terms of the clique number ω, the vertex covering number τ and the diameter d of a graph G. We show that Brouwer's conjecture holds for certain classes of graphs. The Laplacian energy LE(G) of a graph G is defined as LE(G)=∑i=1n|μi−d‾|, where d‾=2mn is the average degree of G. We obtain an upper bound for the Laplacian energy LE(G) of a graph G in terms of the number of vertices n, the number of edges m, the vertex covering number τ and the clique number ω of the graph.
A hole is an induced cycle of length at least 4, and a cap is obtained from a hole by adding a new vertex and joining it to exactly two adjacent vertices of the hole. Let G be a graph containing ...neither caps nor holes of even lengths as induced subgraphs. Cameron et al. (2018) showed that χ(G)≤⌊3ω(G)2⌋, and asked whether χ(G)≤⌈5ω(G)4⌉, where χ(G) and ω(G) denote the chromatic number and clique number of G, respectively. In this paper, we show that χ(G)≤⌈4ω(G)3⌉, and χ(G)≤⌈5ω(G)4⌉ if G further has no 5-cycles sharing exactly one edge. This improves the conclusion of Cameron et al. (2018), and conditionally answers their question in affirmative.
In this paper, we present a sharp upper and lower bounds for the signless Laplacian spectral radius of graphs in terms of clique number. Moreover, the extremal graphs which attain the upper and lower ...bounds are characterized. In addition, these results disprove the two conjectures on the signless Laplacian spectral radius in 8.
In 2013, C. Godsil introduced the quantum version of Hedetniemi's conjecture. To solve this conjecture, we introduce the concept of quantum multiplicative graph and obtain a necessary and sufficient ...condition that a graph is quantum multiplicative. We also examine that the quantum chromatic number of the categorical product of a class of graphs and construct a class of graphs exhibiting separations between clique number and quantum clique number in this paper.
Let c(G), g(G), ω(G) and μn−1(G) denote the number of components, the girth, the clique number and the second smallest Laplacian eigenvalue of the graph G, respectively. The strength η(G) and the ...fractional arboricity γ(G) are defined byη(G)=minF⊆E(G)|F|c(G−F)−c(G)andγ(G)=maxH⊆G|E(H)||V(H)|−1, where the optima are taken over all edge subsets F and all subgraphs H whenever the denominator is non-zero, respectively. Nash-Williams and Tutte proved that G has k edge-disjoint spanning trees if and only if η(G)≥k; and Nash-Williams showed that G can be covered by at most k forests if and only if γ(G)≤k. In this paper, for integers r≥2, s and t, and any simple graph G of order n with minimum degree δ≥2st and either clique number ω(G)≤r or girth g≥3, we prove that if μn−1(G)>2s−1tφ(δ,r) or μn−1(G)>2s−1tN(δ,g), then η(G)≥st, where φ(δ,r)=max{δ+1,⌊rδr−1⌋} and N(δ,g) is the Moore bound on the smallest possible number of vertices such that there exists a δ-regular simple graph with girth g. As corollaries, sufficient conditions on μn−1(G) such that G has k edge-disjoint spanning trees are obtained. Analogous result involving μn−1(G) to characterize fractional arboricity of graphs with given clique number is also presented. Former results in Liu et al. (2014) 17 and Hong et al. (2016) 11 are extended, and the result in Liu et al. (2019) 18 is improved.
Let G be a simple graph with n vertices, m edges and having adjacency eigenvalues λ1 , λ2 , … , λn . The energy E(G) of the graph G is defined as E(G) = ∑i = 1n∣λi∣ . In this paper, we obtain the ...upper bounds for the energy E(G) in terms of the vertex covering number τ , the clique number ω , the number of edges m , maximum vertex degree d1 and second maximum vertex degree d2 of the connected graph G . These upper bounds improve some of the recently known upper bounds.
In this paper, we introduce the zero-divisor graph of a poset with respect to an automorphism, called the generalized zero-divisor graph of a poset, as an extension of the zero-divisor graph of a ...poset. It is proved that for such graphs, the chromatic number and the clique number need not be equal. A sufficient condition is provided for the chromatic number and the clique number of the generalized zero-divisor graph to be equal, which extends the result of the zero-divisor graph of poset. Further, the connectedness, diameter and girth of such graphs are studied.
Let G be a graph of order n with m edges and clique number ω. Let μ1≥μ2≥…≥μn=0 be the Laplacian eigenvalues of G and let σ=σ(G)(1≤σ≤n) be the largest positive integer such that μσ≥2mn. In this paper ...we study the relation between σ and ω. In particular, we provide the answer to Problem 2.3 raised in Pirzada and Ganie (2015) 15. Moreover, we characterize all connected threshold graphs with σ<ω−1, σ=ω−1 and σ>ω−1. We obtain Nordhaus–Gaddum-type results for σ. Some relations between σ with other graph invariants are obtained.
The spectral radius (or the signless Laplacian spectral radius) of a general hypergraph is the maximum modulus of the eigenvalues of its adjacency (or its signless Laplacian) tensor. In this paper, ...we firstly obtain a lower bound of the spectral radius (or the signless Laplacian spectral radius) of general hypergraphs in terms of clique number. Moreover, we present a relation between a homogeneous polynomial and the clique number of general hypergraphs. As an application, we finally obtain an upper bound of the spectral radius of general hypergraphs in terms of clique number.
The annihilator graph $AG(R)$ of a commutative ring $R$ is a simple undirected graph with the vertex set $Z(R)^*$ and two distinct vertices are adjacent if and only if $ann(x) cup ann(y)$ $ neq $ ...$ann(xy)$. In this paper we give the sufficient condition for a graph $AG(R)$ to be complete. We characterize rings for which $AG(R)$ is a regular graph, we show that $gamma (AG(R))in {1,2}$ and we also characterize the rings for which $AG(R)$ has a cut vertex. Finally we find the clique number of a finite reduced ring and characterize the rings for which $AG(R)$ is a planar graph.
PDF
