Contractibility techniques as a closure concept. (English) Zbl 1018.05099
Authors’ abstract: In this paper there is introduced a closure concept in the class of line graphs and claw-free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of P. A. Catlin [J. Graph Theory 12, 29-44 (1988; Zbl 0659.05073)] and H. J. Veldman [Discrete Math. 124, 229-239 (1994; Zbl 0789.05061)] and of the closure concept introduced by the first author [J. Comb. Theory, Ser. B 70, 217-224 (1997; Zbl 0872.05032)]. It is shown that the closure is uniquely determined and the closure operation preserves the circumference of the graph.
Reviewer: Stanislav Jendrol’ (Košice)
Keywords:
closure; contractible graph; collapsible graph; line graph; claw-free graph; Hamiltonian graph; circumferenceReferences:
| [1] | Beineke, J Combin Theory Ser B 9 pp 129– (1970) |
| [2] | Graph theory with applications, Macmillan, London and Elsevier, New York, 1976. |
| [3] | Broersma, Discrete Math 233 pp 55– (2001) |
| [4] | Catlin, J Graph Theory 12 pp 29– (1988) |
| [5] | Harary, Canad. Math Bull 8 pp 701– (1965) |
| [6] | Ryj??ek, J Combin Theory Ser B 70 pp 217– (1997) |
| [7] | Veldman, Discrete Math, 124 pp 229– (1994) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
