Search

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]

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]