Cycle‐Saturated Graphs with Minimum Number of Edges
Cycle‐Saturated Graphs with Minimum Number of Edges
复制标题
DOI：
10.1002/jgt.21668
复制
发表时间：
2011-03
影响因子：
0.9
通讯作者：
Z. Füredi;Younjin Kim
中科院分区：
文献类型：
--
作者：
Z. Füredi;Younjin Kim
一个图G称为H-饱和的，如果它不包含H的任何副本，但对于G的补图中的任何边e，图G+e包含一些H。n顶点H饱和图的最小尺寸记为sat（n，H）。证明了对于所有n≥k≥3，sat（n，Ck）=n+n/k+O（（n/k2）+k2）成立，其中Ck是一个长为k的圈.一个图G是H-半饱和的，如果G+e包含的H的拷贝数比G对e∈E（G <$）包含的H的拷贝数多。设ssat（n，H）是n-顶点H-半饱和图的最小尺寸。我们有ssat（n，Ck）=n+n/（2k）+O（（n/k2）+k）.我们猜想我们的构造对于n> n 0（k）是最优的.© 2012 Wiley Periodicals，Inc.图论73：203-215，2013
A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph G+e contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by sat(n,H) . We prove sat(n,Ck)=n+n/k+O((n/k2)+k2)holds for all n≥k≥3 , where Ck is a cycle with length k. A graph G is H‐semisaturated if G+e contains more copies of H than G does for ∀e∈E(G¯) . Let ssat (n,H) be the minimum size of an n‐vertex H‐semisaturated graph. We have ssat(n,Ck)=n+n/(2k)+O((n/k2)+k).We conjecture that our constructions are optimal for n>n0(k) . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013