Dominating cycles and forbidden pairs containing a path of order 5

Abstract

A cycle is a graph is dominating if every edge of the graph is incident with a vertex of the cycle. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every $2$-connected $\{P_5,K_4^{-}\}$-free graph contains a longest cycle which is a dominating cycle. (ii) Every $2$-connected $\{P_5,W^{\ast }\}$-free graph contains a longest cycle which is a dominating cycle. Here $P_5$ is the path of order $5$, $K_4^{-}$ is the graph obtained from the complete graph of order $4$ by removing one edge, and $W^{\ast }$ is a graph obtained from two triangles and an edge by identifying one vertex in each.

17pages, 7 figures

References in corpus (1)

• Forbidden pairs and the existence of a dominating cycle