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.展开更多
Given a connected graph G,the revised edge-revised Szeged index is defined as Sz_(e)^(*)(G)=∑_(e=uv∈E_(G))(m_(u)(e)+m_(0)(e)/2)(m_(v)(e)+m_(0)(e)/w),where m_(u)(e),m_(v)(e)and m_(0)(e)are the number of edges of G ly...Given a connected graph G,the revised edge-revised Szeged index is defined as Sz_(e)^(*)(G)=∑_(e=uv∈E_(G))(m_(u)(e)+m_(0)(e)/2)(m_(v)(e)+m_(0)(e)/w),where m_(u)(e),m_(v)(e)and m_(0)(e)are the number of edges of G lying closer to vertex u than to vertex u,the number of edges of G lying closer to vertex than to vertex u and the number of edges of G at the same distance to u and u,respectively.In this paper,by transformation and calculation,the lower bound of revised edge-Szeged index of unicyclic graphs with given diameter is obtained,and the extremal graph is depicted.展开更多
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.
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.展开更多
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）.展开更多
The q-Wiener index of unicyclic graphs are determined in this work. As an example of its applications, an explicit expression of q-Wiener index of caterpillar cycles is presented.
In this note, we correct a wrong result in a paper of Das et al. with regard to the comparison between the Wiener index and the Zagreb indices for trees （Das K C, Jeon H, Trinajstic N. The comparison between the Wie...In this note, we correct a wrong result in a paper of Das et al. with regard to the comparison between the Wiener index and the Zagreb indices for trees （Das K C, Jeon H, Trinajstic N. The comparison between the Wiener index and the Zagreb indices and the eccentric connectivity index for trees. Discrete Appl. Math., 2014, 171：35 41）, and give a simple way to compare the Wiener index and the Zagreb indices for trees. Moreover, the comparison between the Wiener index and the Zagreb indices for unicyclic graphs is carried out.展开更多
A graph G is nonsingular if its adjacency matrix A(G)is nonsingular.A nonsingular graph G is said to have an inverse G+if A(G)-1 is signature similar to a nonnegative matrix.Let H be the class of connected bipartite g...A graph G is nonsingular if its adjacency matrix A(G)is nonsingular.A nonsingular graph G is said to have an inverse G+if A(G)-1 is signature similar to a nonnegative matrix.Let H be the class of connected bipartite graphs with unique perfect matchings.We present a characterization of bicyclic graphs in H which possess unicyclic or bicyclic inverses.展开更多
A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic the...A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.展开更多
A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if ...A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim（G）, is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim（G） equals 1, n-1, or n-2, respectively. We give a Nordhaus–Gaddum-type result for the strong metric dimension of a graph and its complement： for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim（G）＋sdim（G）≤2（ n-2）. It is readily seen that sdim（G）＋sdim（G）=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim（G）＋sdim（G）=2（n 2） if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim（G）＋sdim（G）≤2（n-3） if G is a tree; we also show that 4≤sdim（G）＋sdim（G）≤2（n-3） if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim（G）＋sdim（G）=2（n-3） when G is a tree or a unicyclic graph.展开更多
A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a gr...A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.展开更多
基金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.
文摘Given a connected graph G,the revised edge-revised Szeged index is defined as Sz_(e)^(*)(G)=∑_(e=uv∈E_(G))(m_(u)(e)+m_(0)(e)/2)(m_(v)(e)+m_(0)(e)/w),where m_(u)(e),m_(v)(e)and m_(0)(e)are the number of edges of G lying closer to vertex u than to vertex u,the number of edges of G lying closer to vertex than to vertex u and the number of edges of G at the same distance to u and u,respectively.In this paper,by transformation and calculation,the lower bound of revised edge-Szeged index of unicyclic graphs with given diameter is obtained,and the extremal graph is depicted.
基金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.
文摘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.
文摘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）.
基金supported by National Natural Science Foundation of China(11126326)NSF of Guandong Province(S2012010010815)Foundation of Wuyi University(201210041650504)
文摘The q-Wiener index of unicyclic graphs are determined in this work. As an example of its applications, an explicit expression of q-Wiener index of caterpillar cycles is presented.
基金The NSF(11301093,11501139)of Chinathe NSF(2014A030313640)of Guangdong Provincethe Foundation(Yq2014111)for Distinguished Young Talents in Higher Education of Guangdong Province
文摘In this note, we correct a wrong result in a paper of Das et al. with regard to the comparison between the Wiener index and the Zagreb indices for trees （Das K C, Jeon H, Trinajstic N. The comparison between the Wiener index and the Zagreb indices and the eccentric connectivity index for trees. Discrete Appl. Math., 2014, 171：35 41）, and give a simple way to compare the Wiener index and the Zagreb indices for trees. Moreover, the comparison between the Wiener index and the Zagreb indices for unicyclic graphs is carried out.
基金NSFC(Grant No.11761070,61662079)Postgraduate Innovation Project of Xinjiang,Xinjiang Normal University Undergraduate teaching project(SDJG2017-3)The Opening Project of Key Laboratory of Xinjiang Normal University(No:XJNUSYS082017A02).
文摘A graph G is nonsingular if its adjacency matrix A(G)is nonsingular.A nonsingular graph G is said to have an inverse G+if A(G)-1 is signature similar to a nonnegative matrix.Let H be the class of connected bipartite graphs with unique perfect matchings.We present a characterization of bicyclic graphs in H which possess unicyclic or bicyclic inverses.
基金Supported by the National Natural Science Foundation of China (10671081)
文摘A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.
文摘A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim（G）, is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim（G） equals 1, n-1, or n-2, respectively. We give a Nordhaus–Gaddum-type result for the strong metric dimension of a graph and its complement： for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim（G）＋sdim（G）≤2（ n-2）. It is readily seen that sdim（G）＋sdim（G）=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim（G）＋sdim（G）=2（n 2） if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim（G）＋sdim（G）≤2（n-3） if G is a tree; we also show that 4≤sdim（G）＋sdim（G）≤2（n-3） if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim（G）＋sdim（G）=2（n-3） when G is a tree or a unicyclic graph.
基金supported by the Science and Technology Program of Guangzhou,China (No.202002030183)by the Qinghai Province Natural Science Foundation (No.2020-ZJ-924)by the Guangdong Province Natural Science Foundationauthorized in 2020。
文摘A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.
