共查询到20条相似文献,搜索用时 31 毫秒
1.
The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Cn denote the cycle of order n and the graph obtained from joining two cycles C6 by a path Pn-12 with its two leaves. Let Bn denote the class of all bipartite bicyclic graphs but not the graph Ra,b, which is obtained from joining two cycles Ca and Cb (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class Bn. However, they could not determine which of the two graphs Ra,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of Ra,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open. 相似文献
2.
Let G be a graph on n vertices, and let λ1,λ2,…,λn be its eigenvalues. The Estrada index of G is a recently introduced graph invariant, defined as . We establish lower and upper bounds for EE in terms of the number of vertices and number of edges. Also some inequalities between EE and the energy of G are obtained. 相似文献
3.
The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Denote by Cn the cycle, and the unicyclic graph obtained by connecting a vertex of C6 with a leaf of Pn-6. Caporossi et al. conjectured that the unicyclic graph with maximal energy is for n=8,12,14 and n≥16. In Hou et al. (2002) [Y. Hou, I. Gutman, C. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36], the authors proved that is maximal within the class of the unicyclic bipartite n-vertex graphs differing from Cn. And they also claimed that the energies of Cn and is quasi-order incomparable and left this as an open problem. In this paper, by utilizing the Coulson integral formula and some knowledge of real analysis, especially by employing certain combinatorial techniques, we show that the energy of is greater than that of Cn for n=8,12,14 and n≥16, which completely solves this open problem and partially solves the above conjecture. 相似文献
4.
Let G be a graph with n vertices and m edges. Let λ1, λ2, … , λn be the eigenvalues of the adjacency matrix of G, and let μ1, μ2, … , μn be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences. 相似文献
5.
The Estrada index of a graph G is defined as , where λ1,λ2,…,λn are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ1,μ2,…,μn are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively. 相似文献
6.
Mirko Lepovi? 《Discrete Mathematics》2007,307(6):730-738
Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that Ac=[cij] is the conjugate adjacency matrix of the graph G if cij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and cij=0 if i=j. Let PG(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if PG(λ)=PH(λ) and . Further, let Pc(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs Gi=G?i(i=1,2,…,n). If Pc(G)=Pc(H) we prove that , provided that the order of G is greater than 2. 相似文献
7.
For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ1 is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that . 相似文献
8.
Shengbiao Hu 《Discrete Mathematics》2007,307(2):280-284
Let G be a simple graph. Let λ1(G) and μ1(G) denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let Δ denote the largest vertex degree. If G has just one cycle, then
9.
Gui-Xian Tian 《Linear algebra and its applications》2011,435(9):2140-2149
Let D be a digraph of order n and λ1,λ2,…,λn denote all the eigenvalues of the skew-adjacency matrix of D. The skew energy ES(D) of D is defined as . In this paper, it is proved that for any positive integer k≥3, there exists a k-regular graph of order n having an orientation D with . This work positively answers a problem proposed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825-1835]. In addition, a digraph is also constructed such that its skew energy is the same as the energy of its underlying graph. 相似文献
10.
Zhibin Du 《Linear algebra and its applications》2011,435(10):2462-2467
The Estrada index of a graph G is defined as , where λ1,λ2,…,λn are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799-810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree. 相似文献
11.
We find lower bounds on the difference between the spectral radius λ1 and the average degree of an irregular graph G of order n and size e. In particular, we show that, if n ? 4, then
12.
Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γk(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number irk(G). The authors prove that if an irk-set X is a k-independent set of G, then , and that for k?2, if irk(G)=1, if irk(G) is odd, and if irk(G) is even, which generalize some known results. 相似文献
13.
Let G be a graph on n vertices, and let λ1,λ2,…,λn be its eigenvalues. The Estrada index is defined as . We determine the unique tree with maximum Estrada index among the trees on n vertices with given matching number, and the unique tree with maximum Estrada index among the trees on n vertices with fixed diameter. For , we also determine the tree with maximum Estrada index among the trees on n vertices with maximum degree Δ. It gives a partial solution to the conjecture proposed by Ili? and Stevanovi? in Ref. [14]. 相似文献
14.
Wang Qin 《Discrete Mathematics》2005,294(3):303-309
A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K1,3. The kth power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and Tr, r?2, where Tr is the graph with 4r vertices ui,vi,xi,yi, 1?i?r, such that for each i with 1?i?r, {ui,vi,xi,yi} is a clique of Tr and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K4×K2, and . 相似文献
15.
Saieed Akbari Alireza Alipour Javad Ebrahimi Boroojeni Mirhamed Mirjalalieh Shirazi 《Linear algebra and its applications》2007,422(1):341-347
Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that . 相似文献
16.
For a simple graph G, let denote the complement of G relative to the complete graph and let PG(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]PG∇H(x) is represented in terms of PG, , PH and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials. 相似文献
17.
Aneta Dudek 《Discrete Applied Mathematics》2006,154(9):1372-1379
A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is Kn-1∪K1. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph Gn of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and Pm-saturated graphs with small size. 相似文献
18.
Spectral radius and Hamiltonicity of graphs 总被引:1,自引:0,他引:1
Miroslav Fiedler 《Linear algebra and its applications》2010,432(9):2170-2173
Let G be a graph of order n and μ(G) be the largest eigenvalue of its adjacency matrix. Let be the complement of G.Write Kn-1+v for the complete graph on n-1 vertices together with an isolated vertex, and Kn-1+e for the complete graph on n-1 vertices with a pendent edge.We show that:If μ(G)?n-2, then G contains a Hamiltonian path unless G=Kn-1+v; if strict inequality holds, then G contains a Hamiltonian cycle unless G=Kn-1+e.If , then G contains a Hamiltonian path unless G=Kn-1+v.If , then G contains a Hamiltonian cycle unless G=Kn-1+e. 相似文献
19.
Richard Stong 《Discrete Mathematics》2006,306(18):2186-2204
Call a directed graph symmetric if it is obtained from an undirected graph G by replacing each edge of G by two directed edges, one in each direction. We will show that if G has a Hamilton decomposition with certain additional structure, then has a directed Hamilton decomposition. In particular, it will follow that the bidirected cubes for m?2 are decomposable into 2m+1 directed Hamilton cycles and that a product of cycles is decomposable into 2m+1 directed Hamilton cycles if ni?3 and m?2. 相似文献
20.
Weiqi Lin 《Linear algebra and its applications》2011,435(1):152-617
Let G be a graph of order n and the Laplacian characteristic polynomial of G. Zhou and Gutman [19] proved that among all trees of order n, the kth coefficient ck is largest when the tree is a path and is smallest for a star. In this paper, for two given positive integers p and q(p≤q), we characterize the trees with a given bipartition (p,q) which have the minimal and second minimal Laplacian coefficients. 相似文献