\(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
    0 references
    0 references
    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
    0 references
    Hamilton circuit
    0 references
    claw-free graphs
    0 references
    0 references