A proof of a conjecture about Dλ-paths in graphs with large neighborhood unions

AbstractA path P of a graph G is called a Dλ-path if every component of G/V(P) has order less than λ. In particular, a D1-path is a hamiltonian path. Given a graph G, let H1H2 be subgraphs of G, we define the distance between H1 and H2 in G, denoted by d(H1,H2), to be the length of a shortest path in G starting at a vertex of H1 and ending at a vertex of H2. If G contains two connected subgraphs of order λ at distance two, then NC2λ(G) denotes min {|N(H1)UN(H2)| H1 and H2 are connected subgraphs of order λ with d(H1,H2) = 2}; otherwise, NC2;(G) = n - 2λ + 1. Bauer, Fan and Veldman proved that a graph G of order n contains a Dλ-path if G is 2-connected and NC2(G)⩾ (2n + 2)/3 - 2λ. They also conjectured that G contains a Dλ-path if G is 2-connected and NC2i(G) ⩾(n + 3)/2 - 2λ. In this paper, we prove this conjecture is true and the bound (n + 3)/2 - 2λ is best possible. In particular, for λ = 1, it also solves Lindquester's conjecture about hamiltonian paths (D1-paths) in graphs with large neighborhood unions