论文标题
一些大k的最小k因子图
Minimally k-factor-critical graphs for some large k
论文作者
论文摘要
如果删除任何$ k $ vertices的删除会导致完美匹配的图形，则据说$ n $的图$ g $ of订单$ n $ to $ k $ - to $ k $ - to $ n $至关重要的。 $ 1 $ - 和$ 2 $ -FACTOR-关键图形分别是众所周知的关键因素和双向图。如果在e（g）$中的任何边缘$ e \，$ g-e $中的任何边缘$ e \，$ k $ - 因素限制图$ g $都称为最小值。 1998年，O。Favaron和M. Shi猜想，每个最低$ k $ -k $ - 比例的订单$ n $关键图具有最低度$ k+1 $，并以$ k = 1，n-2，n-4 $和$ n-6 $确认了它。在本文中，我们使用一种简单的方法来确定上述结果。作为主要结果，这种方法的进一步使用使人们能够证明猜想是$ k = n-8 $的正确使用。我们还获得了每个最低$（n-6）$ - 关键订单$ n $的因子 - 最多具有$ n-δ（g）$顶点，最高度$δ（g）$ for $ n-4 \leqΔ（g）\ leq n-1 $。
A graph $G$ of order $n$ is said to be $k$-factor-critical for integers $1\leq k < n$, if the removal of any $k$ vertices results in a graph with a perfect matching. $1$- and $2$-factor-critical graphs are the well-known factor-critical and bicritical graphs, respectively. A $k$-factor-critical graph $G$ is called minimal if for any edge $e\in E(G)$, $G-e$ is not $k$-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimally $k$-factor-critical graph of order $n$ has the minimum degree $k+1$ and confirmed it for $k=1, n-2, n-4$ and $n-6$. In this paper, we use a simple method to reprove the above result. As a main result, the further use of this method enables ones to prove the conjecture to be true for $k=n-8$. We also obtain that every minimally $(n-6)$-factor-critical graph of order $n$ has at most $n-Δ(G)$ vertices with the maximum degree $Δ(G)$ for $n-4\leq Δ(G)\leq n-1$.
