論文

査読有り
2013年10月

Forbidden subgraphs generating a finite set

DISCRETE MATHEMATICS
  • Jun Fujisawa
  • ,
  • Michael D. Plummer
  • ,
  • Akira Saito

313
19
開始ページ
1835
終了ページ
1842
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1016/j.disc.2012.05.015
出版者・発行元
ELSEVIER SCIENCE BV

For a set F of connected graphs, a graph G is said to be F-free if G does not contain any member of F as an induced subgraph. The members of F are referred to as forbidden subgraphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow the possibility of the existence of exceptional graphs as long as their number is finite. However, in this type of research, if the set of k-connected F-free graphs itself, denoted by g(k)(F), is finite, then every graph in g(k)(F) logically satisfies all the graph properties, except for possibly a finite number of exceptions. If this occurs, F does not give any information about a particular property. We think that such sets F obscure the view in the study of forbidden subgraphs, and we want to remove them. With this motivation, we study the sets F with finite g(k)(F). We prove that vertical bar F vertical bar <= 2 and g(k)(F) is finite, then either K-1.2 is an element of F or F consists of a complete graph and a star. For each of the values of k, 1 <= k <= 6, we then characterize all the pairs {K-l, K-1,K-m} such that g(k)({K-l, K-1,K-m}) is finite. We also give a complete characterization of F with vertical bar F vertical bar <= 3 and finite g(2)(F). (C) 2012 Elsevier B.V. All rights reserved.

リンク情報
DOI
https://doi.org/10.1016/j.disc.2012.05.015
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000322689800002&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.disc.2012.05.015
  • ISSN : 0012-365X
  • Web of Science ID : WOS:000322689800002

エクスポート
BibTeX RIS