论文标题
最小化$ k_s $饱和图中固定尺寸的匹配数量
Minimizing the number of matchings of fixed size in a $K_s$-saturated graph
论文作者
论文摘要
对于固定的图$ f $，如果$ g $不包含子图的同构为$ f $，则图$ g $被认为是$ f $饱和的，但是在添加任何新的边缘后确实包含$ f $。 令$ m_k $为匹配，由$ k $边缘组成，$ s_ {n，k} $是完整图形$ k_k $的联接图和一个空图$ \ overline {k_ {n-k {n-k}} $。在本文中，我们证明，对于$ s \ geq3 $和$ k \ geq 2 $，$ s_ {n，s-2} $包含所有$ n $ n $ n $ vertex $ k_s $ atatrate图中$ m_k $的最低数量，用于足够大的$ n $，当$ k \ leq s-2 $时，它是唯一的极好图表。此外，我们还表明$ s_ {n，1} $是$ k = 2 $和$ s = 3 $时的唯一极端图。
For a fixed graph $F$, a graph $G$ is said to be $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$ but does contain $F$ after the addition of any new edge. Let $M_k$ be a matching consisting of $k$ edges and $S_{n,k}$ be the join graph of a complete graph $K_k$ and an empty graph $\overline{K_{n-k}}$. In this paper, we prove that for $s \geq3$ and $k\geq 2$, $S_{n,s-2}$ contains the minimum number of $M_k$ among all $n$-vertex $K_s$-saturated graphs for sufficiently large $n$, and when $k \leq s-2$, it is the unique extremal graph. In addition, we also show that $S_{n,1}$ is the unique extremal graph when $k=2$ and $s=3$.
