Search

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]

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: 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]