\(D_ \lambda\)-cycles in \(\lambda\)-claw-free graphs (Q1356724)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(D_ \lambda\)-cycles in \(\lambda\)-claw-free graphs |
scientific article |
Statements
\(D_ \lambda\)-cycles in \(\lambda\)-claw-free graphs (English)
0 references
20 August 1997
0 references
A \(\lambda\)-claw is a connected graph \(H\) such that \(H\) contains a vertex \(v\) and \(H \setminus \{ v \}\) is the union of three pairwise remote, connected subgraphs each of which contains exactly \(\lambda\) vertices. (Note that the \(1\)-claw is \(K_{1,3}\).) A graph \(G\) is called \(\lambda\)-claw-free if no induced subgraph of \(G\) is a \(\lambda\)-claw. Let \(G\) be a \(k\)-connected (\(k \geq 2\)), \(\lambda\)-claw-free graph such that either (i) for every two remote connected subgraphs \(S_1\) and \(S_2\) of \(G\) of order \(\lambda\) we have that \(d(S_1) + d(S_2) > n - (k+1)\lambda - k\), or (ii) for every three pairwise remote, connected subgraphs \(S_1\), \(S_2\), \(S_3\) of \(G\) of order \(\lambda\) we have that \(d(S_1) + d(S_2) + d(S_3) > n - (k+1)\lambda +1\). Then \(G\) contains a circuit \(C\) such that each component of \(G \setminus V(C)\) has at most \(\lambda -1\) vertices.
0 references
Hamilton circuit
0 references
claw-free graphs
0 references