For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Forbidden Subgraphs Generating Almost All Claw-Free Graphs with High Connectivity
Michitaka FURUYA Maho YOKOTA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2019/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Graph algorithms
claw-free graph, forbidden subgraph, Matthews-Sumner conjecture,
Full Text: PDF(780.4KB)>>
For a family H of connected graphs and an integer k≥1, let Gk(H) denote the family of k-connected graphs which contain no element of H as an induced subgraph. Let H+ be the family of those connected graphs of order 5 which contain K1,3 as an induced subgraph. In this paper, for each integer k≥1, we characterize the families H⊆H+ such that the symmetric difference of Gk(K1,3) and Gk(H) is finite.