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]

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]

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]