pith. sign in

arxiv: 1502.02933 · v1 · pith:CEZ4YM4Tnew · submitted 2015-02-10 · 🧮 math.CO

Dominating cycles and forbidden pairs containing a path of order 5

classification 🧮 math.CO
keywords cyclegraphdominatingedgeeveryorderconnectedcontains
0
0 comments X
read the original 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^{*}\}$-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^{*}$ is a graph obtained from two triangles and an edge by identifying one vertex in each.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.