A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(...A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(G) (where V(G) is the vertex number of G and α(G) is its independence number). From this result, we get a necessary and sufficient condition for a vertex-transitive graph to be star extremal as well as a necessary and sufficient condition for a circulant graph to be star extremal. Using these conditions, we obtain several classes of star extremal graphs.展开更多
The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its...The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.展开更多
The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its c...The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .展开更多
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.展开更多
For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant verti...For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant vertices,whereβe{1,2,3,4,n-3,n-2,n-1}.展开更多
With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.
The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
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.展开更多
A connected graph G = （V, E） is called a quasi-tree graph, if there exists a vertex vo ∈ V（G） such that G - v0 is a tree. Liu and Lu [Linear Algebra Appl. 428 （2008） 2708- 2714] determined the maximal spectral ...A connected graph G = （V, E） is called a quasi-tree graph, if there exists a vertex vo ∈ V（G） such that G - v0 is a tree. Liu and Lu [Linear Algebra Appl. 428 （2008） 2708- 2714] determined the maximal spectral radius together with the corresponding graph among all quasi-tree graphs on n vertices. In this paper, we extend their result, and determine the second to the fifth largest spectral radii together with the corresponding graphs among all quasi-tree graphs on n vertices.展开更多
The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this pap...The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this paper, the definition of a class of po- lygonal chains is given, ordering of the polygonal chains with respect to Merrifield-Simmons index and Hosoya index are ob- tained, and their extremal graphs with respect to these two topo- logical indices are determined.展开更多
Let be a graph with n vertices and m edges. The sum of absolute value of all coefficients of matching polynomial is called Hosoya index. In this paper, we determine 2<sup>nd</sup> to 4<sup>th</sup...Let be a graph with n vertices and m edges. The sum of absolute value of all coefficients of matching polynomial is called Hosoya index. In this paper, we determine 2<sup>nd</sup> to 4<sup>th</sup> minimum Hosoya index of a kind of tetracyclic graph, with m = n +3.展开更多
The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, whe...The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, where d( u ) denotes the degree of a vertex u in G. The paper mainly provides the upper and lower bounds of the exponential Randić index in quasi-tree graphs, and characterizes the extremal graphs when the bounds are achieved.展开更多
Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
The Turan number of a graph H,denoted by ex(n,H),is the maximum number of edges in any graph on n vertices containing no H as a subgraph.Let P_(ι)denote the path onιvertices,S_(ι-1)denote the star onιvertices and ...The Turan number of a graph H,denoted by ex(n,H),is the maximum number of edges in any graph on n vertices containing no H as a subgraph.Let P_(ι)denote the path onιvertices,S_(ι-1)denote the star onιvertices and k_(1)P_(ι)∪k_(2)S_(ι-1)denote the path-star forest with disjoint union of k_(1)copies of P_(ι)and k_(2)copies of S_(ι-1).In 2022,[Graphs Combin.,2022,38(3):Paper No.84,16 pp.] raised a conjecture about the Turan number of k_(1)P_(2ι)∪k_(2)S_(2ι-1).In this paper,we determine the Turan numbers of P_(ι)∪kS_(ι-1)and k_(1)P_(2ι)∪k_(2)S_(2ι-1)for n appropriately large,which implies the above conjecture.The corresponding extremal graphs are also completely characterized.展开更多
A feedback vertex set in a graph G\S is a vertex subset S such that is acyclic.The girth of a graph is the minimum cycle length in G.In this paper,some results are proven:(i)Every connected graph G has a feedback vert...A feedback vertex set in a graph G\S is a vertex subset S such that is acyclic.The girth of a graph is the minimum cycle length in G.In this paper,some results are proven:(i)Every connected graph G has a feedback vertex set at most m/3 and the bound is tight if and only if G is K_(3)orK_(4).(ii)Alon et al.(J Graph Theory 38:113–123,2001)proved every connected triangle-free graph G has a feedback vertex set at most m/4.We prove the bound is tight if and only if G is 4-cycle,Square-Claw or Double-Squares.(iii)Every connected outerplanar graph G with girth k has a feedback vertex set at most m/k and the bound is tight if and only if G is a k-cycle.This result verifies the conjecture of Dross et al.(Discrete Appl Math 214:99–107,2016)on outerplanar graph.展开更多
An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we ...An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.展开更多
It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g ＋ k and g...It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g ＋ k and girth g. In 1987, Cao proved that this conjecture is true for k ≥ g（g - 2）/8 and false for k = 2 and sufficiently large g. In this note, we show that g 〉12 suffices for the counterexample and give more counterexamples with large girth for any integer k 〉 1.展开更多
Let G（n,k,t） be a set of graphs with n vertices,k cut edges and t cut vertices.In this paper,we classify these graphs in G（n,k,t） according to cut vertices,and characterize the extremal graphs with the largest spe...Let G（n,k,t） be a set of graphs with n vertices,k cut edges and t cut vertices.In this paper,we classify these graphs in G（n,k,t） according to cut vertices,and characterize the extremal graphs with the largest spectral radius in G（n,k,t）.展开更多
文摘A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(G) (where V(G) is the vertex number of G and α(G) is its independence number). From this result, we get a necessary and sufficient condition for a vertex-transitive graph to be star extremal as well as a necessary and sufficient condition for a circulant graph to be star extremal. Using these conditions, we obtain several classes of star extremal graphs.
文摘The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.
文摘The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .
基金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.
基金Supported by the Zhejiang Provincial Natural Science Foundation of China(102055)Supported by the NSF of China(10471131)Supported by the Foundation of Zhejiang Universities' Youth Teachers
文摘The problem studied in this paper is to determine e（p, C）, the minimum size of a connected graph G with given vertex number p and cut-width C.
文摘For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant vertices,whereβe{1,2,3,4,n-3,n-2,n-1}.
文摘With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.
基金Supported by Natural Science Foundation of Zhejiang Province(1 0 2 0 5 5 )
文摘The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
基金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 National Natural Science Foundation of China(Grant No.11171290)the Natural Science Foundation of Jiangsu Province(Grant No.BK20151295)
文摘A connected graph G = （V, E） is called a quasi-tree graph, if there exists a vertex vo ∈ V（G） such that G - v0 is a tree. Liu and Lu [Linear Algebra Appl. 428 （2008） 2708- 2714] determined the maximal spectral radius together with the corresponding graph among all quasi-tree graphs on n vertices. In this paper, we extend their result, and determine the second to the fifth largest spectral radii together with the corresponding graphs among all quasi-tree graphs on n vertices.
基金Supported by the National Natural Science Foundation of China(11161041)Innovative Team Subsidize of Northwest University for Nationalitiesthe Fundamental Research Funds for the Central Universities(31920140059)
文摘The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this paper, the definition of a class of po- lygonal chains is given, ordering of the polygonal chains with respect to Merrifield-Simmons index and Hosoya index are ob- tained, and their extremal graphs with respect to these two topo- logical indices are determined.
文摘Let be a graph with n vertices and m edges. The sum of absolute value of all coefficients of matching polynomial is called Hosoya index. In this paper, we determine 2<sup>nd</sup> to 4<sup>th</sup> minimum Hosoya index of a kind of tetracyclic graph, with m = n +3.
文摘The exponential Randić index has important applications in the fields of biology and chemistry. The exponential Randić index of a graph G is defined as the sum of the weights e 1 d( u )d( v ) of all edges uv of G, where d( u ) denotes the degree of a vertex u in G. The paper mainly provides the upper and lower bounds of the exponential Randić index in quasi-tree graphs, and characterizes the extremal graphs when the bounds are achieved.
文摘Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
文摘The Turan number of a graph H,denoted by ex(n,H),is the maximum number of edges in any graph on n vertices containing no H as a subgraph.Let P_(ι)denote the path onιvertices,S_(ι-1)denote the star onιvertices and k_(1)P_(ι)∪k_(2)S_(ι-1)denote the path-star forest with disjoint union of k_(1)copies of P_(ι)and k_(2)copies of S_(ι-1).In 2022,[Graphs Combin.,2022,38(3):Paper No.84,16 pp.] raised a conjecture about the Turan number of k_(1)P_(2ι)∪k_(2)S_(2ι-1).In this paper,we determine the Turan numbers of P_(ι)∪kS_(ι-1)and k_(1)P_(2ι)∪k_(2)S_(2ι-1)for n appropriately large,which implies the above conjecture.The corresponding extremal graphs are also completely characterized.
基金supported by the National Natural Science Foundation of China(Nos.11901605,12101069)the disciplinary funding of Central University of Finance and Economics,the Emerging Interdisciplinary Project of CUFE.
文摘A feedback vertex set in a graph G\S is a vertex subset S such that is acyclic.The girth of a graph is the minimum cycle length in G.In this paper,some results are proven:(i)Every connected graph G has a feedback vertex set at most m/3 and the bound is tight if and only if G is K_(3)orK_(4).(ii)Alon et al.(J Graph Theory 38:113–123,2001)proved every connected triangle-free graph G has a feedback vertex set at most m/4.We prove the bound is tight if and only if G is 4-cycle,Square-Claw or Double-Squares.(iii)Every connected outerplanar graph G with girth k has a feedback vertex set at most m/k and the bound is tight if and only if G is a k-cycle.This result verifies the conjecture of Dross et al.(Discrete Appl Math 214:99–107,2016)on outerplanar graph.
基金the National Natural Science Foundation of China(Nos.11922112 and 11771221)the Natural Science Foundation of Tianjin(Nos.20JCZDJC00840 and 20JCJQJC00090)+2 种基金Yong-Xin Lan was partially supported by the National Natural Science Foundation of China(No.12001154)the Natural Science Foundation of Hebei Province(No.A2021202025)the Special Funds for Jointly Building Universities of Tianjin(No.280000307).
文摘An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.
基金Supported by Tsinghua University Initiative Scientific Research Program
文摘It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g ＋ k and girth g. In 1987, Cao proved that this conjecture is true for k ≥ g（g - 2）/8 and false for k = 2 and sufficiently large g. In this note, we show that g 〉12 suffices for the counterexample and give more counterexamples with large girth for any integer k 〉 1.
基金Supported by National Natural Science Foundation of China(Grant No.11071078)
文摘Let G（n,k,t） be a set of graphs with n vertices,k cut edges and t cut vertices.In this paper,we classify these graphs in G（n,k,t） according to cut vertices,and characterize the extremal graphs with the largest spectral radius in G（n,k,t）.
