Dominating cycles in bipartite biclaw-free graphs (Q1903714): Difference between revisions

In a (finite, undirected, simple) graph \(G\) a biclaw is defined to be an induced subgraph isomorphic to the graph obtained from two disjoint copies of the star \(K_{1,3}\) by adding an edge joining the two vertices of degree 3, and a dominating cycle to be a cycle \(C\) such that every edge in \(G\) has at least one end-vertex on \(C\). A bipartite graph \(G\) with vertex-classes \(A\), \(B\) is called balanced iff \(|A|= |B|\). The authors prove the following theorem: If \(G\) is a connected, bipartite, balanced, biclaw-free graph on \(n\) vertices with minimum degree \(\delta\geq 24\) such that \(u\leq 8\delta- 69\), then every longest cycle \(C\) in \(G\) is dominating.