Dominating cycles and forbidden pairs containing P₅

DOI10.1007/S00373-015-1673-8MaRDI QIDQ343722zbMATH OpenOpenAlexFDO

Authors Shuya Chiba, Michitaka Furuya, Shoichi Tsuchiya

Publication date 29 November 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.02933

zbMATH Keywords

dominating cyclesforbidden subgraphsforbidden pairs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

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.

Recommendations

• Forbidden pairs and the existence of a dominating cycle
• Characterizing forbidden pairs for relative length of longest paths and cycles
• Graphs without induced P₅and C₅
• Dominating cycles in triangle-free graphs.
• Dominating cliques in \(P_ 5\)-free graphs

Cites work

• scientific article; zbMATH DE number 4191710 (Why is no real title available?)
• scientific article; zbMATH DE number 3730183 (Why is no real title available?)
• Characterizing forbidden pairs for hamiltonian properties
• Forbidden pairs and the existence of a dominating cycle
• Forbidden subgraphs and Hamiltonian properties and graphs
• Graph theory
• Paw-free graphs

Cited in

(3)

• Forbidden pairs and the existence of a dominating cycle
• Characterizing forbidden pairs for relative length of longest paths and cycles
• Dominating cliques in \(P_ 5\)-free graphs

This page was built for publication: Dominating cycles and forbidden pairs containing \(P_5\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343722)