The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G ...The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G is defined as ME(G) = Pni=1 |λi|. By the famous Coulson’s formula, matching energies can also be calculated by an improper integral depending on a parameter. A k-claw attaching graph Gu(k) refers to the graph obtained by attaching k pendent edges to the graph G at the vertex u, where u is called the root of Gu(k). In this paper, we use some theories of mathematical analysis to obtain a new technique to compare the matching energies of two k-claw attaching graphs Gu(k) and Hv(k) with the same order, that is, limk→∞[ME(Gu(k)) − ME(Hv(k))] = ME(G − u) − ME(H − v). By the technique, we finally determine unicyclic graphs of order n with the 9th to 13th minimal matching energies for all n ≥ 58.展开更多
The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the comple...The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.展开更多
Very recently D.Vukicevic et al.[8]introduced a new topological index for a molecular graph G named Lanzhou index as∑_(u∈V(G))d_(u)d^(2)_(u),where d_(u)and d_(u)denote the degree of vertex u in G and in its compleme...Very recently D.Vukicevic et al.[8]introduced a new topological index for a molecular graph G named Lanzhou index as∑_(u∈V(G))d_(u)d^(2)_(u),where d_(u)and d_(u)denote the degree of vertex u in G and in its complement respectively.Lanzhou index Lz(G)can be expressed as(n-1)M_(1)(G)-F(G),where M_(1)(G)and F(G)denote the first Zagreb index and the forgotten index of G respectively,and n is the number of vertices in G.It turns out that Lanzhou index outperforms M_(1)(G)and F(G)in predicting the logarithm of the octanol-water partition coefficient for octane and nonane isomers.It was shown that stars and balanced double stars are the minimal and maximal trees for Lanzhou index respectively.In this paper,we determine the unicyclic graphs and the unicyclic chemical graphs with the minimum and maximum Lanzhou indices separately.展开更多
Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved t...Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved that all unicyclic graphs H （n; q, n1, n2, n3, n4） are determined by their Laplacian spectra.展开更多
For a simple graph G, the energy E（G） is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un...For a simple graph G, the energy E（G） is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un｜ d（x） = r for any vertex x ∈ V（Cl）}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39（2, 2, 2） ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.展开更多
Let G be a simple connected graph with pendant vertex set ？V and nonpendant vertex set V_0. The signless Laplacian matrix of G is denoted by Q（G）. The signless Dirichlet eigenvalue is a real number λ such that the...Let G be a simple connected graph with pendant vertex set ？V and nonpendant vertex set V_0. The signless Laplacian matrix of G is denoted by Q（G）. The signless Dirichlet eigenvalue is a real number λ such that there exists a function f ≠ 0 on V（G） such that Q（G）f（u） = λf（u） for u ∈ V_0 and f（u） = 0 for u ∈ ？V. The signless Dirichlet spectral radiusλ（G） is the largest signless Dirichlet eigenvalue. In this paper, the unicyclic graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with a given degree sequence are characterized.展开更多
The resistance status of a vertex of a connected graph is the sum of the resistance distance between this vertex and any other vertices of the graph. The minimum(maximum,resp.) resistance status of a connected graph i...The resistance status of a vertex of a connected graph is the sum of the resistance distance between this vertex and any other vertices of the graph. The minimum(maximum,resp.) resistance status of a connected graph is the minimum(maximum, resp.) resistance status of all vertices of the graph. In this paper, we determine the extremal values and corresponding extremal graphs for the minimum(maximum, resp.) resistance status over all unicyclic graphs of fixed order, and we also discuss the dependence of the minimum(maximum, resp.) resistance status on the girth of unicyclic graphs.展开更多
Given a simple graph G,the oriented graph G^(σ)is obtained from G by orienting each edge and G is called the underlying graph of G^(σ).The skew-symmetric adjacency matrix S(G^(σ))of G^(σ),where the(u,v)-entry is 1...Given a simple graph G,the oriented graph G^(σ)is obtained from G by orienting each edge and G is called the underlying graph of G^(σ).The skew-symmetric adjacency matrix S(G^(σ))of G^(σ),where the(u,v)-entry is 1 if there is an arc from u to v,and−1 if there is an arc from v to u(and 0 otherwise),has eigenvalues of 0 or pure imaginary.The k-th-skew spectral moment of Gσis the sum of power k of all eigenvalues of S(G^(σ)),where k is a non-negative integer.The skew spectral moments can be used to produce graph catalogues.In this paper,we researched the skew spectral moments of some oriented trees and oriented unicyclic graphs and produced their catalogues in lexicographical order.We determined the last 2[d/4]oriented trees with underlying graph of diameter d and the last 2[g/4]+1 oriented unicyclic graphs with underlying graph of girth g,respectively.展开更多
The hyper-Wiener index is a kind of extension of the Wiener index,used for predicting physicochemical properties of organic compounds.The hyper-Wiener index W W(G)is defined as WW(G)=1/2∑u,v∈V(G)(dG(u,v)+d^2G(u,v))w...The hyper-Wiener index is a kind of extension of the Wiener index,used for predicting physicochemical properties of organic compounds.The hyper-Wiener index W W(G)is defined as WW(G)=1/2∑u,v∈V(G)(dG(u,v)+d^2G(u,v))with the summation going over all pairs of vertices in G,dG(u,v)denotes the distance of the two vertices u and v in the graph G.In this paper,we study the minimum hyper-Wiener indices among all the unicyclic graph with n vertices and diameter d,and characterize the corresponding extremal graphs.展开更多
Let U be a unicyclic graph of order n,and mU(1)the multiplicity of Laplacian eigenvalue 1 of U.It is well-known that 0 is a simple Lapalcian eigenvalue of connected graph.This means that if U has five Laplacian eigenv...Let U be a unicyclic graph of order n,and mU(1)the multiplicity of Laplacian eigenvalue 1 of U.It is well-known that 0 is a simple Lapalcian eigenvalue of connected graph.This means that if U has five Laplacian eigenvalues different from 0 and 1,then mU(1)=n-6.In this paper,we completely characterize all the unicyclic graphs with mU(1)=n-6.展开更多
Balaban index and Sum-Balaban index were used in various quantitative structureproperty relationship and quantitative structure activity relationship studies. In this paper,the unicyclic graphs with the second largest...Balaban index and Sum-Balaban index were used in various quantitative structureproperty relationship and quantitative structure activity relationship studies. In this paper,the unicyclic graphs with the second largest Balaban index and the second largest SumBalaban index among all unicyclic graphs on n vertices are characterized, respectively.展开更多
Let Gbe a connected graph with vertex set V(G). Then the degree resistance distance of Gis defined as DR(G)=∑{ u,v }⊆V(G)(d(u)+d(v))R(u,v), where d(u)is the degree of the vertex u, and R(u,v)is the degree resistance ...Let Gbe a connected graph with vertex set V(G). Then the degree resistance distance of Gis defined as DR(G)=∑{ u,v }⊆V(G)(d(u)+d(v))R(u,v), where d(u)is the degree of the vertex u, and R(u,v)is the degree resistance distance between uand vin graph G. A unicyclic graph is a connected graph with a unique cycle. In this paper, we characterize the unique graph with the third-maximum degree resistance distance among all unicyclic graphs with nvertices.展开更多
Let Un be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),...,T_(g))Un be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in the anticlockwise direction)by identifying vi with the root of a...Let Un be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),...,T_(g))Un be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in the anticlockwise direction)by identifying vi with the root of a rooted tree Ti of order ni for each i=1,2,...,g,where ni≥1 and∑^(g)_(i=1)n_(i)=n.Let S(n_(1),n_(2),...,n_(g))be obtained from C(T_(1),T_(2),..,T_(g))by replacing each Ti by a rooted star Sni with the center as its root.Let U(n_(1),n_(2),...,ng)be the set of unicyclic graphs which differ from the unicyclic graph S(n_(1),n_(2),...,n_(g))only up to a permutation of ni's.In this paper,the graph with the minimal least signless Laplacian eigenvalue(respectively,the graph with maximum signless Laplacian spread)in U(n_(1),n_(2),...,n_(g))is determined.展开更多
For graphs G and H,the Ramsey number R(G,H)is the minimum integer N such that any coloring of the edges of the complete graph K_(N)in red or blue yields a red G or a blue H.Denote the union of t disjoint copies of a g...For graphs G and H,the Ramsey number R(G,H)is the minimum integer N such that any coloring of the edges of the complete graph K_(N)in red or blue yields a red G or a blue H.Denote the union of t disjoint copies of a graph F by tF.We call tK_(2)a stripe.In this paper,we completely determine Ramsey numbers of stripes versus trees and unicyclic graphs.Our result also implies that a tree is tK_(2)-good if and only if the independence number of this tree is no less than t.As an application,we improve the known Ramsey numbers of stars versus fan graphs.Moreover,we determine the bipartite Ramsey numbers of a connected bipartite graph versus stripes.展开更多
The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ 1(U)=n or λ 1(U...The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ 1(U)=n or λ 1(U)∈(n,n+1] are characterized.展开更多
The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.
The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a gr...The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a graph G is the minimum eardinality of a set S of black vertices （whereas vertices in V（G）／S are colored white） such that V（G） is turned black after finitely many applications of ＂the color-change rule＂： a white vertex is converted black if it is the only white neighbor of a black vertex. We show that dim（T） ≤Z（T） for a tree T, and that dim（G）≤Z（G）＋I if G is a unicyclic graph; along the way, we characterize trees T attaining dim（T） = Z（T）. For a general graph G, we introduce the ＂cycle rank conjecture＂. We conclude with a proof of dim（T） - 2 ≤ dim（T ＋ e） ≤dim（T） ＋ 1 for e∈ E（T）.展开更多
Let U^(g)_(n)be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),…,T_(g))∈U^(g)_(n)be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in an anticlockwise direction)by identifying v_(i)with...Let U^(g)_(n)be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),…,T_(g))∈U^(g)_(n)be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in an anticlockwise direction)by identifying v_(i)with the root of a rooted tree T_(i)of order n_(i)for each i=1,2,…,g,where n_(i)≥1 and∑^(g)_(i=1)n_(i)=n.In this note,the graph with the minimal least eigenvalue(and the graph with maximal spread)in C(T_(1),T_(2),…,T_(g))is determined.展开更多
The number of zero eigenvalues in the spectrum of the graph G is called its nullity and is denoted by η（G）. In this paper, we determine the all extremal unicyclic graphs achieving the fifth upper bound n - 6 and th...The number of zero eigenvalues in the spectrum of the graph G is called its nullity and is denoted by η（G）. In this paper, we determine the all extremal unicyclic graphs achieving the fifth upper bound n - 6 and the sixth upperbound n - 7.展开更多
基金Supported by the National Natural Science Foundation of China(Nos.12271439,11871398)the National College Students Innovation and Entrepreneurship Training Program(No.201910699173)。
文摘The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G is defined as ME(G) = Pni=1 |λi|. By the famous Coulson’s formula, matching energies can also be calculated by an improper integral depending on a parameter. A k-claw attaching graph Gu(k) refers to the graph obtained by attaching k pendent edges to the graph G at the vertex u, where u is called the root of Gu(k). In this paper, we use some theories of mathematical analysis to obtain a new technique to compare the matching energies of two k-claw attaching graphs Gu(k) and Hv(k) with the same order, that is, limk→∞[ME(Gu(k)) − ME(Hv(k))] = ME(G − u) − ME(H − v). By the technique, we finally determine unicyclic graphs of order n with the 9th to 13th minimal matching energies for all n ≥ 58.
基金Supported by the National Natural Science Foundation of China(11861011,11501133,11661010)。
文摘The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.
基金Supported by the National Natural Science Foundation of China(11871256)the Chinese-Croatian bilateral project(7-22)。
文摘Very recently D.Vukicevic et al.[8]introduced a new topological index for a molecular graph G named Lanzhou index as∑_(u∈V(G))d_(u)d^(2)_(u),where d_(u)and d_(u)denote the degree of vertex u in G and in its complement respectively.Lanzhou index Lz(G)can be expressed as(n-1)M_(1)(G)-F(G),where M_(1)(G)and F(G)denote the first Zagreb index and the forgotten index of G respectively,and n is the number of vertices in G.It turns out that Lanzhou index outperforms M_(1)(G)and F(G)in predicting the logarithm of the octanol-water partition coefficient for octane and nonane isomers.It was shown that stars and balanced double stars are the minimal and maximal trees for Lanzhou index respectively.In this paper,we determine the unicyclic graphs and the unicyclic chemical graphs with the minimum and maximum Lanzhou indices separately.
基金the National Natural Science Foundation of China(Grant No.11171273)Graduate StartingSeed Fund of Northwestern Polytechnical University(Grant No.Z2014173)
文摘Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved that all unicyclic graphs H （n; q, n1, n2, n3, n4） are determined by their Laplacian spectra.
基金Supported by the National Natural Science Foundation of China(Grant No.11326216)the Docter Foundationof Shandong University of Technology(Grant No.413010)
文摘For a simple graph G, the energy E（G） is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un｜ d（x） = r for any vertex x ∈ V（Cl）}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39（2, 2, 2） ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1127125611601208)
文摘Let G be a simple connected graph with pendant vertex set ？V and nonpendant vertex set V_0. The signless Laplacian matrix of G is denoted by Q（G）. The signless Dirichlet eigenvalue is a real number λ such that there exists a function f ≠ 0 on V（G） such that Q（G）f（u） = λf（u） for u ∈ V_0 and f（u） = 0 for u ∈ ？V. The signless Dirichlet spectral radiusλ（G） is the largest signless Dirichlet eigenvalue. In this paper, the unicyclic graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with a given degree sequence are characterized.
基金Supported by the National Natural Science Foundation of China(Grant No.12071158)。
文摘The resistance status of a vertex of a connected graph is the sum of the resistance distance between this vertex and any other vertices of the graph. The minimum(maximum,resp.) resistance status of a connected graph is the minimum(maximum, resp.) resistance status of all vertices of the graph. In this paper, we determine the extremal values and corresponding extremal graphs for the minimum(maximum, resp.) resistance status over all unicyclic graphs of fixed order, and we also discuss the dependence of the minimum(maximum, resp.) resistance status on the girth of unicyclic graphs.
基金Supported by the Research Project of Jianghan University(Grant No.2021yb056)the National Natural Science Foundation of China(Grant Nos.1197115812061039).
文摘Given a simple graph G,the oriented graph G^(σ)is obtained from G by orienting each edge and G is called the underlying graph of G^(σ).The skew-symmetric adjacency matrix S(G^(σ))of G^(σ),where the(u,v)-entry is 1 if there is an arc from u to v,and−1 if there is an arc from v to u(and 0 otherwise),has eigenvalues of 0 or pure imaginary.The k-th-skew spectral moment of Gσis the sum of power k of all eigenvalues of S(G^(σ)),where k is a non-negative integer.The skew spectral moments can be used to produce graph catalogues.In this paper,we researched the skew spectral moments of some oriented trees and oriented unicyclic graphs and produced their catalogues in lexicographical order.We determined the last 2[d/4]oriented trees with underlying graph of diameter d and the last 2[g/4]+1 oriented unicyclic graphs with underlying graph of girth g,respectively.
基金Supported by the National Natural Science Foundation of China(Grant No.11871077)the Natural Science Foundation of Anhui Province(Grant No.1808085MA04)the Natural Science Foundation of Department of Education of Anhui Province(Grant No.KJ2017A362)。
文摘The hyper-Wiener index is a kind of extension of the Wiener index,used for predicting physicochemical properties of organic compounds.The hyper-Wiener index W W(G)is defined as WW(G)=1/2∑u,v∈V(G)(dG(u,v)+d^2G(u,v))with the summation going over all pairs of vertices in G,dG(u,v)denotes the distance of the two vertices u and v in the graph G.In this paper,we study the minimum hyper-Wiener indices among all the unicyclic graph with n vertices and diameter d,and characterize the corresponding extremal graphs.
基金Supported by the National Natural Science Foundation of China(Grant No.11961041)Excellent postgraduates of Gansu Provincial Department of Education“Star of innovation”Foundation(Grant No.2021CXZX-594).
文摘Let U be a unicyclic graph of order n,and mU(1)the multiplicity of Laplacian eigenvalue 1 of U.It is well-known that 0 is a simple Lapalcian eigenvalue of connected graph.This means that if U has five Laplacian eigenvalues different from 0 and 1,then mU(1)=n-6.In this paper,we completely characterize all the unicyclic graphs with mU(1)=n-6.
基金Supported by the Natural Science Foundation of Anhui Province(Grant No.1508085MC55)the Natural Science Foundation of Educational Government of Anhui Province(Grant No.KJ2013A076)
文摘Balaban index and Sum-Balaban index were used in various quantitative structureproperty relationship and quantitative structure activity relationship studies. In this paper,the unicyclic graphs with the second largest Balaban index and the second largest SumBalaban index among all unicyclic graphs on n vertices are characterized, respectively.
基金Supported by the National Natural Science Foundation of China(Grant Nos.6137902111471077)+4 种基金the Natural Science Foundation of Fujian Province(Grant Nos.2015J010182016J01673)the Project of Fujian Education Department(Grant No.JZ160455)Research Fund of Minnan Normal University(Grant No.MX1603)Faculty Research Grant of Hong Kong Baptist University
文摘In this paper, a necessary and sufficient condition for a unicyclic graph with a perfect matching having signless Laplacian eigenvalue 2 is deduced.
文摘Let Gbe a connected graph with vertex set V(G). Then the degree resistance distance of Gis defined as DR(G)=∑{ u,v }⊆V(G)(d(u)+d(v))R(u,v), where d(u)is the degree of the vertex u, and R(u,v)is the degree resistance distance between uand vin graph G. A unicyclic graph is a connected graph with a unique cycle. In this paper, we characterize the unique graph with the third-maximum degree resistance distance among all unicyclic graphs with nvertices.
基金This research is supported by NSFC(Nos.12171154,12301438)the Chenguang Program of Shanghai Education Development Foundation and Shanghai Municipal Education Commission(No.23CGA37)。
文摘Let Un be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),...,T_(g))Un be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in the anticlockwise direction)by identifying vi with the root of a rooted tree Ti of order ni for each i=1,2,...,g,where ni≥1 and∑^(g)_(i=1)n_(i)=n.Let S(n_(1),n_(2),...,n_(g))be obtained from C(T_(1),T_(2),..,T_(g))by replacing each Ti by a rooted star Sni with the center as its root.Let U(n_(1),n_(2),...,ng)be the set of unicyclic graphs which differ from the unicyclic graph S(n_(1),n_(2),...,n_(g))only up to a permutation of ni's.In this paper,the graph with the minimal least signless Laplacian eigenvalue(respectively,the graph with maximum signless Laplacian spread)in U(n_(1),n_(2),...,n_(g))is determined.
基金supported by the National Natural Science Foundation of China(No.11931002).
文摘For graphs G and H,the Ramsey number R(G,H)is the minimum integer N such that any coloring of the edges of the complete graph K_(N)in red or blue yields a red G or a blue H.Denote the union of t disjoint copies of a graph F by tF.We call tK_(2)a stripe.In this paper,we completely determine Ramsey numbers of stripes versus trees and unicyclic graphs.Our result also implies that a tree is tK_(2)-good if and only if the independence number of this tree is no less than t.As an application,we improve the known Ramsey numbers of stars versus fan graphs.Moreover,we determine the bipartite Ramsey numbers of a connected bipartite graph versus stripes.
基金Supported by the project item for young teachers of colleges and universities of Anhui province( 2 0 0 3jq1 0 1 ) and the project item of Anhui University for talents group construction
文摘The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ 1(U)=n or λ 1(U)∈(n,n+1] are characterized.
基金Supported by the Project of Talent Introduction for Graduates of Chizhou University (Grant No2009RC011)
文摘The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.
文摘The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a graph G is the minimum eardinality of a set S of black vertices （whereas vertices in V（G）／S are colored white） such that V（G） is turned black after finitely many applications of ＂the color-change rule＂： a white vertex is converted black if it is the only white neighbor of a black vertex. We show that dim（T） ≤Z（T） for a tree T, and that dim（G）≤Z（G）＋I if G is a unicyclic graph; along the way, we characterize trees T attaining dim（T） = Z（T）. For a general graph G, we introduce the ＂cycle rank conjecture＂. We conclude with a proof of dim（T） - 2 ≤ dim（T ＋ e） ≤dim（T） ＋ 1 for e∈ E（T）.
文摘Let U^(g)_(n)be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),…,T_(g))∈U^(g)_(n)be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in an anticlockwise direction)by identifying v_(i)with the root of a rooted tree T_(i)of order n_(i)for each i=1,2,…,g,where n_(i)≥1 and∑^(g)_(i=1)n_(i)=n.In this note,the graph with the minimal least eigenvalue(and the graph with maximal spread)in C(T_(1),T_(2),…,T_(g))is determined.
基金Supported by the National Natural Science Foundation of China (Grant No10861009)
文摘The number of zero eigenvalues in the spectrum of the graph G is called its nullity and is denoted by η（G）. In this paper, we determine the all extremal unicyclic graphs achieving the fifth upper bound n - 6 and the sixth upperbound n - 7.
