Dominating cycles and forbidden pairs containing P₅

DOI10.1007/S00373-015-1673-8zbMATH Open1351.05124arXiv1502.02933OpenAlexW2255270643MaRDI QIDQ343722FDOQ343722

Authors: Shuya Chiba, Michitaka Furuya, Shoichi Tsuchiya 

Publication date: 29 November 2016

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

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^{*}$ is a graph obtained from two triangles and an edge by identifying one vertex in each.

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

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

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)

Cites Work

• Graph theory
• Characterizing forbidden pairs for hamiltonian properties
• Paw-free graphs
• Forbidden subgraphs and Hamiltonian properties and graphs
• Forbidden pairs and the existence of a dominating cycle
• Title not available (Why is that?)
• Title not available (Why is that?)

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)