A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vert...A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.展开更多
[App1.Anal.Discrete Math.,2017,11(1):81-107] defined the A_α-matrix of a graph G as A_α(G)=αD(G)+(1-α)A(G),where α∈[0,1],D(G) and A(G) are the diagonal matrix of degrees and the adjacency matrix of G,respectivel...[App1.Anal.Discrete Math.,2017,11(1):81-107] defined the A_α-matrix of a graph G as A_α(G)=αD(G)+(1-α)A(G),where α∈[0,1],D(G) and A(G) are the diagonal matrix of degrees and the adjacency matrix of G,respectively.The largest eigenvalue of A_α(G) is called the A_α-spectral radius of G,denoted by ρ_α(G).In this paper,we give an upper bound on ρ_α(G) of a Hamiltonian graph G with m edges for α∈[1/2,1),and completely characterize the corresponding extremal graph in the case when m is odd.In order to complete the proof of the main result,we give a sharp upper bound on the ρ_α(G) of a connected graph G in terms of its degree sequence.展开更多
Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has ...Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has at least one common adjacent vertex. Our results improve some known upper bounds. The main tool we use here is the Lagrange identity.展开更多
Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations ...Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.展开更多
A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge ...A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.展开更多
Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d_(1), d_(2),..., d_(n)}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)^(3). Usin...Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d_(1), d_(2),..., d_(n)}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)^(3). Using the properties of inequality, we investigate the bounds of AZI for connected graphs, in particular unicyclic graphs in this paper, some useful conclusions are obtained.展开更多
The atom-bond connectivity（ABC） index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC（G） =∑ uv∈E（G） √d u＋dv-2 dudv,...The atom-bond connectivity（ABC） index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC（G） =∑ uv∈E（G） √d u＋dv-2 dudv,where du denotes the degree of a vertex u in G.A chemical graph is a graph in which no vertex has degree greater than 4.In this paper,we obtain the sharp upper and lower bounds on ABC index of chemical bicyclic graphs.展开更多
A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if t...A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.展开更多
Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 fo...Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.展开更多
Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is les...Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is less than zero. In this paper, we present some upper bounds of reverse total signed vertex domination number of a graph and the exact values of reverse total signed vertex domination number of circles, paths and stars are given.展开更多
Let G be a simple undirected graph.For any real numberα∈[0,1],Nikiforov defined the A_(α)-matrix of G as A_(α)(G)=αD(G)+(1-α)A(G)in 2017,where A(G)and D(G)are the adjacency matrix and the degree diagonal matrix ...Let G be a simple undirected graph.For any real numberα∈[0,1],Nikiforov defined the A_(α)-matrix of G as A_(α)(G)=αD(G)+(1-α)A(G)in 2017,where A(G)and D(G)are the adjacency matrix and the degree diagonal matrix of G,respectively.In this paper,we obtain a lower bound on the A_(α)-spectral radius of a C_(3)-free graph forα∈[0,1)and a sharp upper bound on the Aα-spectral radius of a C_(3)-free k-cycle graph forα∈[1/2,1).展开更多
For the subset S■V(G), if every path with k vertices in a graph G contains at least one vertex from S, we call that S is a k-path vertex cover set of the graph G. Obviously, the subset is not unique. The cardinality ...For the subset S■V(G), if every path with k vertices in a graph G contains at least one vertex from S, we call that S is a k-path vertex cover set of the graph G. Obviously, the subset is not unique. The cardinality of the minimum k-path vertex cover set of a graph G is called the k-path vertex cover number, we denote it by ψk(G). In this paper, a lower or upper bound of ψk for some Cartesian product graphs is presented.展开更多
Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of ...Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.展开更多
文摘A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.
文摘[App1.Anal.Discrete Math.,2017,11(1):81-107] defined the A_α-matrix of a graph G as A_α(G)=αD(G)+(1-α)A(G),where α∈[0,1],D(G) and A(G) are the diagonal matrix of degrees and the adjacency matrix of G,respectively.The largest eigenvalue of A_α(G) is called the A_α-spectral radius of G,denoted by ρ_α(G).In this paper,we give an upper bound on ρ_α(G) of a Hamiltonian graph G with m edges for α∈[1/2,1),and completely characterize the corresponding extremal graph in the case when m is odd.In order to complete the proof of the main result,we give a sharp upper bound on the ρ_α(G) of a connected graph G in terms of its degree sequence.
基金Supported by the National Natural Science Foundation of China(11471077)the Open Research Fund of Key Laboratory of Spatial Data Mining and Information Sharing of MOE(2018LSDMIS09)Foundation of Key Laboratory of Intelligent Metro of Universities in Fujian Province(53001703)
文摘Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has at least one common adjacent vertex. Our results improve some known upper bounds. The main tool we use here is the Lagrange identity.
基金Supported by the National Natural Science Foundation of China(10771080)by the Fund of Fuzhou Uni-versity(XRC-0956)by the Natural Science Foundation of Fujian Province(2010J05005)
文摘Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.
基金Supported by the National Natural Science Foundation of China(10971198)the Zhejiang Natural Science Foundation of China(Z6110786)
文摘A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.
基金Supported by the National Natural Science Foundation of China (Grant No. 61672356)the Teaching Reform Research Project of Shaoyang University (Grant No. 2017JG19)。
文摘Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d_(1), d_(2),..., d_(n)}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)^(3). Using the properties of inequality, we investigate the bounds of AZI for connected graphs, in particular unicyclic graphs in this paper, some useful conclusions are obtained.
基金Supported by the National Natural Science Foundation of China(11071272,10831001,11171279,11101087)the Young Talent Foundation of Fuzhou University(XRC-1154)
文摘The atom-bond connectivity（ABC） index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC（G） =∑ uv∈E（G） √d u＋dv-2 dudv,where du denotes the degree of a vertex u in G.A chemical graph is a graph in which no vertex has degree greater than 4.In this paper,we obtain the sharp upper and lower bounds on ABC index of chemical bicyclic graphs.
文摘A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.
基金supported by the National Natural Science Foundation of China (Grant No.10571117)the Development Foundation of Shanghai Municipal Education Commission (Grant No.05AZ04)
文摘Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.
文摘Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is less than zero. In this paper, we present some upper bounds of reverse total signed vertex domination number of a graph and the exact values of reverse total signed vertex domination number of circles, paths and stars are given.
基金Supported by the National Natural Science Foundation of China(Grant Nos.12071411,12171222)。
文摘Let G be a simple undirected graph.For any real numberα∈[0,1],Nikiforov defined the A_(α)-matrix of G as A_(α)(G)=αD(G)+(1-α)A(G)in 2017,where A(G)and D(G)are the adjacency matrix and the degree diagonal matrix of G,respectively.In this paper,we obtain a lower bound on the A_(α)-spectral radius of a C_(3)-free graph forα∈[0,1)and a sharp upper bound on the Aα-spectral radius of a C_(3)-free k-cycle graph forα∈[1/2,1).
基金Supported by the National Natural Science Foundation of China(Grant Nos.61463026,61463027).
文摘For the subset S■V(G), if every path with k vertices in a graph G contains at least one vertex from S, we call that S is a k-path vertex cover set of the graph G. Obviously, the subset is not unique. The cardinality of the minimum k-path vertex cover set of a graph G is called the k-path vertex cover number, we denote it by ψk(G). In this paper, a lower or upper bound of ψk for some Cartesian product graphs is presented.
基金Project supported by the National Natural Science Foundation of China （Grant No.10571117）, and the Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.
