Forbidden Subgraphs Generating Almost All Claw-Free Graphs with High Connectivity

Michitaka FURUYA  Maho YOKOTA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.987-993
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.987
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Graph algorithms
Keyword: 
claw-free graph,  forbidden subgraph,  Matthews-Sumner conjecture,  

Full Text: PDF(780.4KB)>>
Buy this Article




Summary: 
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 HH+ such that the symmetric difference of Gk(K1,3) and Gk(H) is finite.