BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The planar Turán number of a graph H, denoted exP(n,H), is the maximum number of edges in a planar graph on n vertices without containing H as a subgraph. This notion was introduced by Dowden in 2016 and has attracted quite some attention since then; those work mainly focus on finding exP(n,H) when H is a cycle or Theta graph or H has maximum degree at least four. In this paper, we study exP(n,H) when H is a cubic graph or disjoint union of cycles or H=Ks,t.
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no induced subgraph isomorphic to H1 or H2. Let Pt be the path on t vertices. A graph G is k-vertex-critical if G has chromatic number k but every proper induced subgraph of G has chromatic number less than k. The study of k-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is (k−1)-colorable. In this paper, we initiate a systematic study of the finiteness of k-vertex-critical graphs in subclasses of P5-free graphs. Our main result is a complete classification of the finiteness of k-vertex-critical graphs in the class of (P5,H)-free graphs for all graphs H on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs H using various techniques -- such as Ramsey-type arguments and the dual of Dilworth's Theorem -- that may be of independent interest.
The star chromatic index of a multigraph G, denoted χst′(G), is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. We survey the results of determining the star chromatic index, present the interesting proofs and techniques, and collect many open problems and conjectures.
For a graph G=(V,E), a double Roman dominating function (DRDF) is a function f:V→{0,1,2,3} having the property that if f(v)=0, then vertex v must have at least two neighbors assigned 2 under f or {at least} one neighbor u with f(u)=3, and if f(v)=1, then vertex v must have at least one neighbor u with f(u)≥2. In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF f such that ∑v∈Vf(v) is minimum. We propose {five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations.} Further, we prove that {the first four models indeed solve the double Roman domination problem, and the last two models} are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an H(2(Δ+1))-approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance.
A rooted tree is called a k-ary tree, if all non-leaf vertices have exactly k children, except possibly one non-leaf vertex has at most k−1 children. Denote by h(k) the minimum integer such that every tournament of order at least h(k) contains a k-ary spanning tree. It is well-known that every tournament contains a Hamiltonian path, which implies that h(1)=1. Lu et al. [J. Graph Theory {\bf 30}(1999) 167--176] proved the existence of h(k), and showed that h(2)=4 and h(3)=8. The exact values of h(k) remain unknown for k≥4. A result of Erdős on the domination number of tournaments implies h(k)=Ω(klogk). In this paper, we prove that h(4)=10 and h(5)≥13.
A semi-proper orientation of a given graph G, denoted by (D,w), is an orientation D with a weight function w:A(D)→Z+, such that the in-weight of any adjacent vertices are distinct, where the in-weight of v in D, denoted by wD−(v), is the sum of the weights of arcs towards v. The semi-proper orientation number of a graph G, denoted by χs(G), is the minimum of maximum in-weight of v in D over all semi-proper orientation (D,w) of G. This parameter was first introduced by Dehghan (2019). When the weights of all edges eqaul to one, this parameter is equal to the proper orientation number of G. The optimal semi-proper orientation is a semi-proper orientation (D,w) such that maxv∈V(G)wD−(v)=χs(G). Araújo et al. (2016) showed that χ(G)≤7 for every cactus G and the bound is tight. We prove that for every cactus G, χs(G)≤3 and the bound is tight. Araújo et al. (2015) asked whether there is a constant c such that χ(G)≤c for all outerplanar graphs G. While this problem remains open, we consider it in the weighted case. We prove that for every outerplanar graph G, χs(G)≤4 and the bound is tight.
A bridgeless graph G is called 3-flow-critical if it does not admit a nowhere-zero 3-flow, but G/e has for any e∈E(G). Tutte's 3-flow conjecture can be equivalently stated as that every 3-flow-critical graph contains a vertex of degree three. In this paper, we study the structure and extreme edge density of 3-flow-critical graphs. We apply structure properties to obtain lower and upper bounds on the density of 3-flow-critical graphs, that is, for any 3-flow-critical graph G on n vertices, 58n−2≤∣E(G)∣≤4n−10, where each equality holds if and only if G is K4. We conjecture that every 3-flow-critical graph on n≥7 vertices has at most 3n−8 edges, which would be tight if true. For planar graphs, the best possible density upper bound of 3-flow-critical graphs on n vertices is 25n−8, known from a result of Kostochka and Yancey (JCTB 2014) on vertex coloring 4-critical graphs by duality.
The k-independence number of a graph G is the maximum size of a set of vertices at pairwise distance greater than k. In this paper, for each positive integer k, we prove sharp upper bounds for the k-independence number in an n-vertex connected graph with given minimum and maximum degree.
The χ-stability index esχ(G) of a graph G is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of G. In this paper three open problems from [European J.\ Combin.\ 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of k-regular (k≤5) graphs G with esχ(G)=1 does not extend to k≥6. Graphs G with χ(G)=3 for which esχ(G)+esχ(G)=2 holds are characterized. Necessary conditions on graphs G which attain a known upper bound on esχ(G) in terms of the order and the chromatic number of G are derived. The conditions are proved to be sufficient when n≡2(mod3) and χ(G)=3.
The star chromatic index of a multigraph G, denoted χs′(G), is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bi-colored. A multigraph G is star k-edge-colorable if χs′(G)≤k. Dvořák, Mohar and Šámal [Star chromatic index, J Graph Theory 72 (2013), 313--326] proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than 7/3 is star list-5-edge-colorable. It is known that a graph with maximum average degree 14/5 is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than 12/5 is star 5-edge-colorable.
Graph polynomials are polynomials assigned to graphs. Interestingly, they also arise in many areas outside graph theory as well. Many properties of graph polynomials have been widely studied. In this paper, we survey some results on the derivative and real roots of graph polynomials, which have applications in chemistry, control theory and computer science. Related to the derivatives of graph polynomials, polynomial reconstruction of the matching polynomial is also introduced.
A sparse version of Mantel's Theorem is that, for sufficiently large p, with high probability (w.h.p.), every maximum triangle-free subgraph of G(n,p) is bipartite. DeMarco and Kahn proved this for p>Klogn/n for some constant K, and apart from the value of the constant, this bound is the best possible. Denote by T3 the 3-uniform hypergraph with vertex set {a,b,c,d,e} and edge set {abc,ade,bde}. Frankl and Füredi showed that the maximum 3-uniform hypergraph on n vertices containing no copy of T3 is tripartite for n>3000. For some integer k, let Gk(n,p) be the random k-uniform hypergraph. Balogh et al. proved that for p>Klogn/n for some constant K, every maximum T3-free subhypergraph of G3(n,p) w.h.p. is tripartite and it does not hold when p=0.1logn/n. Denote by T4 the 4-uniform hypergraph with vertex set {1,2,3,4,5,6,7} and edge set {1234,1235,4567}. Pikhurko proved that there is an n0 such that for all n≥n0, the maximum 4-uniform hypergraph on n vertices containing no copy of T4 is 4-partite. In this paper, we extend this type of extremal problem in random 4-uniform hypergraphs. We show that for some constant K and p>Klogn/n, w.h.p. every maximum T4-free subhypergraph of G4(n,p) is 4-partite.
Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let G be a simple graph of order n and μ1,μ2,…,μn be the roots of its matching polynomial. The matching energy of G is defined to be the sum of the absolute values of μi (i=1,2,…,n). In this paper, we characterize the graphs with minimal matching energy among all unicyclic and bicyclic graphs with a given diameter d.
For a given simple graph G, the energy of G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix, which was defined by I. Gutman. The problem on determining the maximal energy tends to be complicated for a given class of graphs. There are many approaches on the maximal energy of trees, unicyclic graphs and bicyclic graphs, respectively. Let Pn6,6,6 denote the graph with n≥20 vertices obtained from three copies of C6 and a path Pn−18 by adding a single edge between each of two copies of C6 to one endpoint of the path and a single edge from the third C6 to the other endpoint of the Pn−18. Very recently, Aouchiche et al. [M. Aouchiche, G. Caporossi, P. Hansen, Open problems on graph eigenvalues studied with AutoGraphiX, {\it Europ. J. Comput. Optim.} {\bf 1}(2013), 181--199] put forward the following conjecture: Let G be a tricyclic graphs on n vertices with n=20 or n≥22, then E(G)≤E(Pn6,6,6) with equality if and only if G≅Pn6,6,6. Let G(n;a,b,k) denote the set of all connected bipartite tricyclic graphs on n vertices with three vertex-disjoint cycles Ca, Cb and Ck, where n≥20. In this paper, we try to prove that the conjecture is true for graphs in the class G∈G(n;a,b,k), but as a consequence we can only show that this is true for most of the graphs in the class except for 9 families of such graphs.
The matching polynomial of a graph is the generating function of the numbers of its matchings with respect to their cardinality. A graph polynomial is polynomial reconstructible, if its value for a graph can be determined from its values for the vertex-deleted subgraphs of the same graph. This note discusses the polynomial reconstructibility of the matching polynomial. We collect previous results, prove it for graphs with pendant edges and disprove it for some graphs.
Gutman and Wagner proposed the concept of the matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let G be a simple graph of order n and μ1,μ2,…,μn be the roots of its matching polynomial. The matching energy of G is defined to be the sum of the absolute values of μi (i=1,2,…,n). Gutman and Cvetkoić determined the tricyclic graphs on n vertices with maximal number of matchings by a computer search for small values of n and by an induction argument for the rest. Based on this result, in this paper, we characterize the graphs with the maximal value of matching energy among all tricyclic graphs, and completely determine the tricyclic graphs with the maximal matching energy. We prove our result by using Coulson-type integral formula of matching energy, which is similar as the method to comparing the energies of two quasi-order incomparable graphs.
Given p≥0 and a graph G whose degree sequence is d1,d2,…,dn, let ep(G)=∑i=1ndip. Caro and Yuster introduced a Turán-type problem for ep(G): given p≥0, how large can ep(G) be if G has no subgraph of a particular type. Denote by exp(n,H) the maximum value of ep(G) taken over all graphs with n vertices that do not contain H as a subgraph. Clearly, ex1(n,H)=2ex(n,H), where ex(n,H) denotes the classical Turán number, i.e., the maximum number of edges among all H-free graphs with n vertices. Pikhurko and Taraz generalize this Turán-type problem: let f be a non-negative increasing real function and ef(G)=∑i=1nf(di), and then define exf(n,H) as the maximum value of ef(G) taken over all graphs with n vertices that do not contain H as a subgraph. Observe that exf(n,H)=ex(n,H) if f(x)=x/2, exf(n,H)=exp(n,H) if f(x)=xp. Bollobás and Nikiforov mentioned that it is important to study concrete functions. They gave an example f(x)=ϕ(k)=(kx), since ∑i=1n(kdi) counts the (k+1)-vertex subgraphs of G with a dominating vertex. Denote by Tr(n) the r-partite Turán graph of order n. In this paper, using the Bollobás--Nikiforov's methods, we give some results on exϕ(n,Kr+1) (r≥2) as follows: for k=1,2, exϕ(n,Kr+1)=eϕ(Tr(n)); for each k, there exists a constant c=c(k) such that for every r≥c(k) and sufficiently large n, exϕ(n,Kr+1)=eϕ(Tr(n)); for a fixed (r+1)-chromatic graph H and every k, when n is sufficiently large, we have exϕ(n,H)=eϕ(n,Kr+1)+o(nk+1).
A new turán-type problem on distances on graphs was introduced by Tyomkyn and Uzzell. In this paper, we focus on the case that the distance is two. We primely show that for any value of n, a graph on n vertices without three vertices pairwise at distance 2, if it has a vertex v∈V(G), whose neighbours are covered by at most two cliques, then it has at most (n2−1)/4+1 pairs of vertices at distance 2. This partially answers a guess of Tyomkyn and Uzzell [Tyomkyn, M., Uzzell, A.J.: A new Turán-Type promble on distaces of graphs. Graphs Combin. {\bf 29}(6), 1927--1942 (2012)].
Let G be a graph with degree sequence d1,d2,…,dn. Given a positive integer p, denote by ep(G)=∑i=1ndip. Caro and Yuster introduced a Turán-type problem for ep(G): given an integer p, how large can ep(G) be if G has no subgraph of a particular type. They got some results for the subgraph of particular type to be a clique of order r+1 and a cycle of even length, respectively. Denote by exp(n,H) the maximum value of ep(G) taken over all graphs with n vertices that do not contain H as a subgraph. Clearly, ex1(n,H)=2ex(n,H), where ex(n,H) denotes the classical Turán number. In this paper, we consider exp(n,C5) and prove that for any positive integer p and sufficiently large n, there exists a constant c=c(p) such that the following holds: if exp(n,C5)=ep(G) for some C5-free graph G of order n, then G is a complete bipartite graph having one vertex class of size cn+o(n) and the other (1−c)n+o(n).
The Turán number of a k-uniform hypergraph H, denoted by exk(n;H), is the maximum number of edges in any k-uniform hypergraph F on n vertices which does not contain H as a subgraph. Let Cℓ(k) denote the family of all k-uniform minimal cycles of length ℓ, S(ℓ1,…,ℓr) denote the family of hypergraphs consisting of unions of r vertex disjoint minimal cycles of length ℓ1,…,ℓr, respectively, and Cℓ(k) denote a k-uniform linear cycle of length ℓ. We determine precisely exk(n;S(ℓ1,…,ℓr)) and exk(n;Cℓ1(k),…,Cℓr(k)) for sufficiently large n. The results extend recent results of Füredi and Jiang who determined the Turán numbers for single k-uniform minimal cycles and linear cycles.
A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in 1965. This connection and its extensions were applied in Turán problems of graphs and uniform hypergraphs. Very recently, the study of Turán densities of non-uniform hypergraphs has been motivated by extremal poset problems. In this paper, we give some Motzkin-Straus type results for non-uniform hypergraphs.
Let Tn be the set of trees with n vertices. Suppose that each tree in Tn is equally likely. We show that the number of different rooted trees of a tree equals (μr+o(1))n for almost every tree of Tn, where μr is a constant. As an application, we show that the number of any given pattern in Tn is also asymptotically normally distributed with mean ∼μMn and variance ∼σMn, where μM,σM are some constants related to the given pattern. This solves an open question claimed in Kok's thesis.
The generalized connectivity of a graph G was introduced by Chartrand et al. Let S be a nonempty set of vertices of G, and κ(S) be defined as the largest number of internally disjoint trees T1,T2,⋯,Tk connecting S in G. Then for an integer r with 2≤r≤n, the {\it generalized r-connectivity} κr(G) of G is the minimum κ(S) where S runs over all the r-subsets of the vertex set of G. Obviously, κ2(G)=κ(G), is the vertex connectivity of G, and hence the generalized connectivity is a natural generalization of the vertex connectivity. Similarly, let λ(S) denote the largest number k of pairwise edge-disjoint trees T1,T2,…,Tk connecting S in G. Then the {\it generalized r-edge-connectivity} λr(G) of G is defined as the minimum λ(S) where S runs over all the r-subsets of the vertex set of G. Obviously, λ2(G)=λ(G). In this paper, we study the generalized 3-connectivity of random graphs and prove that for every fixed integer k≥1, p=nlogn+(k+1)loglogn−logloglogn is a sharp threshold function for the property κ3(G(n,p))≥k, which could be seen as a counterpart of Bollobás and Thomason's result for vertex connectivity. Moreover, we obtain that δ(G(n,p))−1=λ(G(n,p))−1=κ(G(n,p))−1≤κ3(G(n,p))≤λ3(G(n,p))≤κ(G(n,p))=λ(G(n,p))=δ(G(n,p)) almost surely holds, which could be seen as a counterpart of Ivchenko's result.
A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u,v of distinct vertices, G contains a rainbow u−v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G)≤srvc(G) for any nontrivial connected graph G. In this paper, sharp upper and lower bounds of srvc(G) are given for a connected graph G of order n, that is, 0≤srvc(G)≤n−2. Graphs of order n such that srvc(G)=1,2,n−2 are characterized, respectively. It is also shown that, for each pair a,b of integers with a≥5 and b≥(7a−8)/5, there exists a connected graph G such that rvc(G)=a and srvc(G)=b.
For a given simple graph G, the energy of G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Pnℓ be the unicyclic graph obtained by connecting a vertex of Cℓ with a leaf of Pn−ℓ\,. In [G. Caporossi, D. Cvetković, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy, {\it J. Chem. Inf. Comput. Sci.} {\bf 39}(1999) 984--996], Caporossi et al. conjectured that the unicyclic graph with maximal energy is Cn if n≤7 and n=9,10,11,13,15\,, and Pn6 for all other values of n. In this paper, by employing the Coulson integral formula and some knowledge of real analysis, especially by using certain combinatorial technique, we completely solve this conjecture. However, it turns out that for n=4 the conjecture is not true, and P43 should be the unicyclic graph with maximal energy.
The concept of generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in recent years. In our early paper, extremal theory for this graph parameter was started. We determined the minimal number of edges of a graph of order n with κ3=2, i.e., for a graph G of order n and size e(G) with κ3(G)=2, we proved that e(G)≥(6/5)n, and the lower bound is sharp by constructing a class of graphs, only for n≡0 (mod 5) and n=10. In this paper, we improve the lower bound to ⌈(6/5)n⌉. Moreover, we show that for all n≥4 but n=9,10, there always exists a graph of order n with κ3=2 whose size attains the lower bound ⌈(6/5)n⌉. Whereas for n=9,10 we give examples to show that ⌈(6/5)n⌉+1 is the best possible lower bound. This gives a clear picture on the minimal size of a graph of order n with generalized connectivity κ3=2.
For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacent matrix. For Δ≥3 and t≥3, denote by Ta(Δ,t) (or simply Ta) the tree formed from a path Pt on t vertices by attaching Δ−1 P2's on each end of the path Pt, and Tb(Δ,t) (or simply Tb) the tree formed from Pt+2 by attaching Δ−1 P2's on an end of the Pt+2 and Δ−2 P2's on the vertex next to the end. In [X. Li, X. Yao, J. Zhang and I. Gutman, Maximum energy trees with two maximum degree vertices, J. Math. Chem. 45(2009), 962--973], Li et al. proved that among trees of order n with two vertices of maximum degree Δ, the maximal energy tree is either the graph Ta or the graph Tb, where t=n+4−4Δ≥3. However, they could not determine which one of Ta and Tb is the maximal energy tree. This is because the quasi-order method is invalid for comparing their energies. In this paper, we use a new method to determine the maximal energy tree. It turns out that things are more complicated. We prove that the maximal energy tree is Tb for Δ≥7 and any t≥3, while the maximal energy tree is Ta for Δ=3 and any t≥3. Moreover, for Δ=4, the maximal energy tree is Ta for all t≥3 but t=4, for which Tb is the maximal energy tree. For Δ=5, the maximal energy tree is Tb for all t≥3 but t is odd and 3≤t≤89, for which Ta is the maximal energy tree. For Δ=6, the maximal energy tree is Tb for all t≥3 but t=3,5,7, for which Ta is the maximal energy tree. One can see that for most Δ, Tb is the maximal energy tree, Δ=5 is a turning point, and Δ=3 and 4 are exceptional cases.
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. It was proved that computing rc(G) is an NP-Hard problem, as well as that even deciding whether a graph has rc(G)=2 is NP-Complete. It is known that deciding whether a given edge-colored graph is rainbow connected is NP-Complete. We will prove that it is still NP-Complete even when the edge-colored graph is a planar bipartite graph. We also give upper bounds of the rainbow connection number of outerplanar graphs with small diameters. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. It is known that deciding whether a given vertex-colored graph is rainbow vertex-connected is NP-Complete. We will prove that it is still NP-Complete even when the vertex-colored graph is a line graph.
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 Pn6,6 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 a≡b≡2(mod4)) by an edge. In [I. Gutman, D. Vidović, Quest for molecular graphs with maximal energy: a computer experiment, {\it J. Chem. Inf. Sci.} {\bf41}(2001), 1002--1005], Gutman and Vidović conjectured that the bicyclic graph with maximal energy is Pn6,6, for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, {\it Linear Algebra Appl.} {\bf427}(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 Pn6,6 has the maximal value of energy. In [B. Furtula, S. Radenković, I. Gutman, Bicyclic molecular graphs with the greatest energy, {\it J. Serb. Chem. Soc.} {\bf73(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 Pn6,6 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.
A vertex-colored graph is {\it rainbow vertex-connected} if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection} of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. In this paper, we study the computational complexity of vertex-rainbow connection of graphs and prove that computing rvc(G) is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether rvc(G)=2. We also prove that the following problem is NP-Complete: given a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected.
Let G be a nontrivial connected graph of order n and k an integer with 2≤k≤n. For a set S of k vertices of G, let κ(S) denote the maximum number ℓ of edge-disjoint trees T1,T2,...,Tℓ in G such that V(Ti)∩V(Tj)=S for every pair i,j of distinct integers with 1≤i,j≤ℓ. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by κk(G), of G is defined by κk(G)=min{κ(S)}, where the minimum is taken over all k-subsets S of V(G). Thus κ2(G)=κ(G), where κ(G) is the connectivity of G. This paper mainly focuses on the minimal number of edges of a graph G with κ3(G)=2. For a graph G of order v(G) and size e(G) with κ3(G)=2, we obtain that e(G)≥6/5v(G), and the lower bound is sharp by showing a class of examples attaining the lower bound.
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 Pn6 the unicyclic graph obtained by connecting a vertex of C6 with a leaf of Pn−6\,. Caporossi et al. conjecture that the unicyclic graph with maximal energy is Pn6 for n=8,12,14 and n≥16. In``Y. Hou, I. Gutman and C. Woo, Unicyclic graphs with maximal energy, {\it Linear Algebra Appl.} {\bf 356}(2002), 27--36", the authors proved that E(Pn6) is maximal within the class of the unicyclic bipartite n-vertex graphs differing from Cn\,. And they also claimed that the energy of Cn and Pn6 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 Pn6 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.
A conjecture of AutoGraphiX on the relation between the Randić index R and the algebraic connectivity a of a connected graph G is: aR≤(2n−3+22)/(2(1−cosnπ)) with equality if and only if G is Pn, which was proposed by Aouchiche and Hansen [M. Aouchiche and P. Hansen, A survey of automated conjectures in spectral graph theory, {\it Linear Algebra Appl.} {\bf 432}(2010), 2293--2322]. We prove that the conjecture holds for all trees and all connected graphs with edge connectivity κ′(G)≥2, and if κ′(G)=1, the conjecture holds for sufficiently large n. The conjecture also holds for all connected graphs with diameter D≤π22(n−3+22) or minimum degree δ≥2n. We also prove R⋅a≥nD28n−1 and R⋅a≥2(n−1)nδ(2δ−n+2), and then R⋅a is minimum for the path if D≤(n−1)1/4 or δ≥2n−1.
A vertex-colored graph is {\it rainbow vertex-connected} if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection} of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Krivelevich and Yuster proved that if G is a graph of order n with minimum degree δ, then rvc(G)<11n/δ. In this paper, we show that rvc(G)≤3n/(δ+1)+5 for δ≥n−1−1 and n≥290, while rvc(G)≤4n/(δ+1)+5 for 16≤δ≤n−1−2 and rvc(G)≤4n/(δ+1)+C(δ) for 6≤δ≤15, where C(δ)=eδ−33log(δ3+2δ2+3)−3(log3−1)−2. We also prove that rvc(G)≤3n/4−2 for δ=3, rvc(G)≤3n/5−8/5 for δ=4 and rvc(G)≤n/2−2 for δ=5. Moreover, an example shows that when δ≥n−1−1 and δ=3,4,5, our bounds are seen to be tight up to additive factors.
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G)≤3(n+1)/5 for all 3-connected graphs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.