Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646966 | Discrete Mathematics | 2015 | 11 Pages |
Abstract
A cycle CC in a graph GG is called dominating if every edge of GG is incident with a vertex of CC. For a set HH of connected graphs, a graph GG is said to be HH-free if GG does not contain any member of HH as an induced subgraph. When |H|=2|H|=2, HH is called a forbidden pair. In this paper, we investigate the set H of forbidden pairs HH which satisfies that every 2-connected HH-free graph has a dominating cycle. In particular, we show that H is a very small class and find some maximal forbidden pairs of H.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Shuya Chiba, Michitaka Furuya, Shoichi Tsuchiya,