Dominating cycles in bipartite biclaw-free graphs (Q1903714)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dominating cycles in bipartite biclaw-free graphs |
scientific article |
Statements
Dominating cycles in bipartite biclaw-free graphs (English)
0 references
5 June 1996
0 references
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.
0 references
biclaw
0 references
star
0 references
dominating cycle
0 references
bipartite graph
0 references
longest cycle
0 references