Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs
type: Item
instance of: scholarly article
title: Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs
zbMATH Open document ID: 0852.05062
DOI: 10.1007/BF02104806
author: Alexander Ageev
published in: Siberian Mathematical Journal
publication date: 1996-11-25T00:00:00Z
review text: An undirected graph is called \(K_{1, 3}\)-free, if it contains no induced subgraph isomorphic to the complete bipartite graph \(K_{1, 3}\). The class of \(K_{1, 3}\)-free graphs includes all the line graphs and is well studied in many aspects. For instance, it is known that, for \(K_{1, 3}\)-free graphs, the strong Berge conjecture holds, and certain problems that are NP-complete in the general setting are polynomially solvable for them. Since the middle of the 70s articles have begun to appear that are devoted to the study of conditions sufficient for Hamiltonicity of a \(K_{1,3}\)-free graph. It is the following conjecture extending Thomassen's conjecture for line graphs that became widely known: Every 4-connected \(K_{1, 3}\)-free graph is Hamiltonian. It is known that the Hamiltonian cycle problem is NP-complete for 3-connected cubic planar graphs. Plummer and Pulleyblank showed that there exist infinitely many non-Hamiltonian 3-connected cubic graphs that, moreover, possess no dominating cycles. It is easy to observe that the replacement of vertices with triangles transforms a 3-connected cubic graph into a 3-connected \(K_{1,3}\)-free graph; moreover, the former is Hamiltonian if and only if such is the latter. Consequently, the above-cited assertions for 3-connected cubic graphs are also valid for the 3-connected \(K_{1,3}\)-free graphs. Every Hamiltonian graph is, obviously, 2-connected. In the theorem below, we list some conditions each of which guarantees the existence of a Hamiltonian cycle in a 2-connected \(K_{1,3}\)-free graph. Theorem 1.1. Let \(G\) be a 2-connected \(K_{1,3}\)-free graph with \(n\) vertices. The graph \(G\) is Hamiltonian if at least one of the following conditions holds: (c 1) the subgraph induced by \(N(x)\) is connected for every vertex \(x\in V(G)\); (c 2) \(\delta(G)\geq (n- 2)/3\); (c 3) the diameter of \(G\) does not exceed 2; (c 4) for every triple of pairwise nonadjacent vertices \(\{x, y, z\}\subseteq V(G)\), \(\deg(x)+ \d…
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 917058
zbMATH Keywords: Hamiltonicity
zbMATH Keywords: Thomassen's conjecture
zbMATH Keywords: Hamiltonian cycle problem
zbMATH Keywords: dominating cycles
zbMATH Keywords: cubic graphs
MaRDI profile type: Publication
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: Updating the hamiltonian problem—A survey
cites work: Q3097395
cites work: Hamiltonian results inK1,3-free graphs
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Q3967559
cites work: Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
cites work: Longest paths and cycles in K1,3-free graphs
cites work: Hamilton cycles in claw-free graphs
cites work: A generalization of Dirac's theorem for \(K(1,3)\)-free graphs
description: scientific article; zbMATH DE number 917058