BROWSE

Related Scientist

Abhishek, Methuku's photo.

Abhishek, Methuku
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Few H copies in F-saturated graphs

Cited 0 time in webofscience Cited 0 time in scopus
9 Viewed 0 Downloaded
Title
Few H copies in F-saturated graphs
Author(s)
Jürgen Kritschgau; Abhishek Methuku; Michael Tait; Craig Timmons
Publication Date
2020-07
Journal
JOURNAL OF GRAPH THEORY, v.94, no.3, pp.320 - 348
Publisher
WILEY-BLACKWELL
Abstract
© 2019 Wiley Periodicals, Inc. A graph is F-saturated if it is F-free but the addition of any edge creates a copy of F. In this paper we study the function sat(n,H,F) which is the minimum number of copies of H that an F-saturated graph on n vertices may contain. This function is a natural saturation analogue of Alon and Shikhelman's generalized Turan problem, and letting H=K2 recovers the well-studied saturation function. We provide a first investigation into this general function focusing on the cases where the host graph is either Ks or Ck-saturated. Some representative interesting behavior is: For any natural number m, there are graphs H and F such that sat(n,H,F)=Theta(nm). For many pairs k and l, we show sat(n,Cl,Ck)=0. In particular, we prove that there exists a triangle-free Ck-saturated graph on n vertices for any k>4 and large enough n. sat(n,K3,K4)=n-2, sat(n,C4,K4)similar to n22, and sat(n,C6,K5)similar to n3. (a)(b)(c) We discuss several intriguing problems that remain unsolved
URI
https://pr.ibs.re.kr/handle/8788114/7797
DOI
10.1002/jgt.22525
ISSN
0364-9024
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse