Search

For a 2-connected graph G on n vertices and two vertices x , y ∈ V (G) , we prove that there is an (x , y) -path of length at least k , if there are at least n − 1 2 vertices in V (G) \ { x , y } of degree at least k. This strengthens a celebrated theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with n vertices contains a cycle of length at least 2 k , if it has at least n 2 + k vertices of degree at least k. This confirms a 1975 conjecture made by Woodall. As other applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond. [ABSTRACT FROM AUTHOR]

Let H be a class of given graphs. A graph G is said to be H -free if G contains no induced copies of H for every H ∈ H . A graph is called traceable if it contains a Hamilton path. Faudree and Gould (1997) characterized all the pairs { R , S } of connected subgraphs such that every connected { R , S } -free graph is traceable. Li and Vrána (2016) first consider the disconnected forbidden subgraphs, and characterized all pairs of disconnected forbidden subgraphs for hamiltonicity. In this article, we characterize all pairs { R , S } of graphs such that there exists an integer n 0 such that every connected { R , S } -free graph of order at least n 0 is traceable. [ABSTRACT FROM AUTHOR]

In 1962, Erdős gave a sufficient condition for Hamilton cycles in terms of the vertex number, edge number and minimum degree of graphs which generalized Ore’s theorem. One year later, Moon and Moser gave an analogous result for Hamilton cycles in balanced bipartite graphs. In this paper, we present the spectral analogues of Erdős’ theorem and Moon–Moser’s theorem, respectively. Letbe the class of non-Hamiltonian graphs of ordernand minimum degree at leastk. We determine the maximum (signless Laplacian) spectral radius of graphs in(for large enoughn), and the minimum (signless Laplacian) spectral radius of the complements of graphs in. All extremal graphs with the maximum (signless Laplacian) spectral radius and with the minimum (signless Laplacian) spectral radius of the complements are determined, respectively. We also solve similar problems for balanced bipartite graphs and the quasi-complements. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a $$k$$ -connected graph with $$k\ge 2$$ . In this paper we first prove that: For two distinct vertices $$x$$ and $$z$$ in $$G$$ , it contains a path connecting $$x$$ and $$z$$ which passes through its any $$k-2$$ specified vertices with length at least the average degree of the vertices other than $$x$$ and $$z$$ . Further, with this result, we prove that: If $$G$$ has $$n$$ vertices and $$m$$ edges, then it contains a cycle of length at least $$2m/(n-1)$$ passing through its any $$k-1$$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition. [ABSTRACT FROM AUTHOR]

Let G be a graph. For a given graph H , we say that G is H - free if G contains no copies of H as an induced subgraph. Suppose that G is 2-connected, has n vertices, and α is a real number with 0 ≤ α ≤ 1 . In this paper, we characterize the connected graphs R such that G being R -free implies that every longest cycle of G passes through all vertices with degree at least α n + O ( 1 ) in G . [ABSTRACT FROM AUTHOR]

Abstract: Let be an edge-colored graph. The color degree of a vertex of , is defined as the number of colors of the edges incident to . The color number of is defined as the number of colors of the edges in . A rainbow triangle is one in which every pair of edges have distinct colors. In this paper we give some sufficient conditions for the existence of rainbow triangles in edge-colored graphs in terms of color degree, color number and edge number. As a corollary, a conjecture proposed by Li and Wang [H. Li and G. Wang, Color degree and heterochromatic cycles in edge-colored graphs, European J. Combin. 33 (2012) 1958–1964] is confirmed. [Copyright &y& Elsevier]

Abstract: A graph is called homogeneously traceable if for every vertex of , contains a Hamilton path starting from . For a graph , we say that is -free if contains no induced subgraph isomorphic to . For a family of graphs, is called -free if is -free for every . Determining families of graphs such that every -free graph has some graph property has been a popular research topic for several decades, especially for Hamiltonian properties, and more recently for properties related to the existence of graph factors. In this paper we give a complete characterization of all pairs of connected graphs such that every 2-connected -free graph is homogeneously traceable. [Copyright &y& Elsevier]

Abstract: Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs. [Copyright &y& Elsevier]

Let t 1 , … , t r ∈ [ 4 , 2 q ] be any r even integers, where q ≥ 2 and r ≥ 1 are two integers. In this note, we show that every bipartite tournament with minimum outdegree at least q r − 1 contains r vertex-disjoint directed cycles of lengths t 1 ′ , … , t r ′ such that t i ′ = t i for t i = 0 ( mod 4 ) and t i ′ ∈ { t i , t i + 2 } for t i = 2 ( mod 4 ) , where 1 ≤ i ≤ r . The special case q = 2 of the result verifies the bipartite tournament case of a conjecture proposed by Bermond and Thomassen, stating that every digraph with minimum outdegree at least 2 r − 1 contains at least r vertex-disjoint directed cycles. [ABSTRACT FROM AUTHOR]

Abstract: A weighted digraph is a digraph such that every arc is assigned a nonnegative number, called the weight of the arc. The weighted outdegree of a vertex in a weighted digraph is the sum of the weights of the arcs with as their tail, and the weight of a directed cycle in is the sum of the weights of the arcs of . In this note we prove that if every vertex of a weighted digraph with order has weighted outdegree at least 1, then there exists a directed cycle in with weight at least . This proves a conjecture of Bollobás and Scott up to a constant factor. [Copyright &y& Elsevier]