Dominating cycles in bipartite biclaw-free graphs Original Research Article

Flandrin et al. (to appear) define a simple bipartite graph to be biclaw-free if it contains no induced subgraph isomorphic to H, where H could be obtained from two copies of K1,3 by adding an edge joining the two vertices of degree 3. They have shown that if G is a bipartite, balanced, biclaw-free connected graph of order at most 6δ–10, then G is hamiltonian. In this paper we show that if G is a bipartite, balanced, biclaw-free connected graph of order at most 8δ–69, where δ ⩾ 24, then every longest cycle in G is dominating, i.e., every edge has at least one end-vertex on the cycle.