Hamiltonicity in claw-free graphs through induced bulls (Q1893171): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
| (One intermediate revision by one other user not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3211339 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Updating the hamiltonian problem—A survey / rank | |||
Normal rank | |||
Latest revision as of 14:09, 23 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hamiltonicity in claw-free graphs through induced bulls |
scientific article |
Statements
Hamiltonicity in claw-free graphs through induced bulls (English)
0 references
3 July 1995
0 references
A claw is the complete bipartite graph \(K_{1, 3}\) and a bull is the unique graph with the degree sequence 3, 3, 2, 1, 1. A graph \(G\) is claw- free if \(G\) contains no induced subgraph isomorphic to the claw. In this paper, the following conjecture proposed by \textit{H. Broersma} and \textit{H. J. Veldman} [Contemporary methods in graph theory. In honour of Prof. Dr. K. Wagner, 181-194 (1990; Zbl 0723.05082)] is proved: Let \(G\) be a 2- connected claw-free graph. Suppose that, for each induced bull \(B\) in \(G\), the degree one vertices of \(B\) have some common neighbor in \(G\). Then \(G\) contains a Hamilton cycle.
0 references
claw
0 references
bull
0 references
induced subgraph
0 references
claw-free graph
0 references
Hamilton cycle
0 references
