K       1,3    -Free图上的弦泛圈性

doi:10.12677/aam.2024.135187

期刊菜单

$K_{1, 3}$ -Free图上的弦泛圈性
Chorded Pancyclicity on

K_{1, 3}

-Free Graph

DOI: 10.12677/aam.2024.135187, PDF, HTML, XML, 下载: 52 浏览: 119 科研立项经费支持
作者: 李欢, 杨卫华^*：太原理工大学数学学院，山西太原；田增娴：成都信息工程大学应用数学学院，四川成都
关键词: -Free；弦圈；泛圈；弦泛圈；哈密尔顿；-Free； Chorded Cycle； Pancyclic； Chorded Pancyclic； Hamiltonian

摘要: 一个非诱导圈被称为弦圈，即在图中至少有一条额外的边连接圈内两个非相邻的顶点。一个阶数为n的图G, 如果G包含长度为从4到n的弦圈，则称为弦泛圈图。1991年，R.J. Faudree, R.J. Gould和T.E. Lindquester得出结论：令G是阶数为n(n≥14)的2-连通，K1,3-free图。如果对于每一对不相邻的顶点x,y，有|N(x)∪N(y)|≥2n−23，则G是泛圈图。在本文中，我们扩展了这个结果，把泛圈性推广到弦泛圈性：对于任意2-连通，阶数为n(n≥34)的K1,3-free图G，如果每对不相邻顶点x,y∈V(G)，满足|N(x)∪N(y)|≥2n−23，则图G是弦泛圈图。

Abstract: A non-induced cycle is called a chorded cycle, that is, a cycle that has at least one additional edge connecting two non-consecutive vertices within the cycle. A graph G of order n is chorded pancyclic if G contains a chorded cycle of each length from 4 to n. In 1991, R.J. Faudree, R.J. Gould, and T.E. Lindquester concluded: Let G be a 2-connectedK1,3-free graph with the ordern(n≥14). If|N(x)∪N(y)|≥2n−23for each pair of nonadjacent verticesx,y, then G is pancyclic. In this paper, we extended this result by generalizing the concept of pancyclicto chorded pancyclic: ever 2-connected,K1,3-free graph G with ordern≥43is chorded pancyclic if the number of the union of for each pair of nonadjacent vertices at least2n−23.

文章引用：李欢, 田增娴, 杨卫华.

K_{1, 3}

-Free图上的弦泛圈性[J]. 应用数学进展, 2024, 13(5): 1994-1999. https://doi.org/10.12677/aam.2024.135187

1. 引言

本文讨论的所有图都是有限的，无向且没有环和多重边的图。设G是一个图， $V (G)$ 表示图G的顶点集， $E (G)$ 表示图G的边集。对于G的子图H和点 $x \in V (G)$ ，令 $N_{H} (x) = {v \in V (H) | x v \in E (G)}$ ，即 $N_{H} (x) = V (H) \cap N_{G} (x)$ 。G的顶点v的度(或次) $d_{G} (v)$ 是指G中与v关联的边的数目。令 $d_{H} (x) = | N_{H} (x) |$ 。如果没有歧义， $N (x)$ 表示 $N_{G} (x)$ ， $d (x)$ 表示 $d_{G} (x)$ 。对于图G的顶点集S， $G [S]$ 表示由S导出的子图。路(或圈)的长度是路(或圈)中边的数目。对于一个图G，用 $δ (G)$ 表示G的最小度， $δ (G) =$ $\min {d (v) | v \in V (G)}$ 。 $C_{m}$ 表示长度为m的圈，m为正整数。其他未加说明的定义可见参考文献 [1] 。

经过G中每个顶点恰好一次的圈(路)被称为哈密尔顿圈(路) (Hamiltonian Cycle (Path))。如果图G包含哈密尔顿圈，则称图G为哈密尔顿的。一个阶数为n的图被称为泛圈的(Pancyclic)，如果它包含从3到n的所有长度的圈。一个圈的弦(Chord)是指圈中一对不相邻顶点之间的边。如果一个圈至少有一条弦，我们称这样的圈为弦圈(Chorded Cycle)。一个阶数为n的图G是弦泛圈的(Chorded Pancyclic)，如果G包含从4到n的所有长度的弦圈。一个图G是可追踪的(Traceable)，如果存在一条包含G中所有顶点的路，即在G中包含一条哈密尔顿路。

令H为图G的子图。给定一个图族 $F = {H_{1}, H_{2}, \dots, H_{K}}$ ，如果图G没有同构于任何由 $H_{i}$ 的顶点导出的子图，其中 $i = 1, 2, \dots, k$ ，则我们称图G是F-free的。特别地，如果 $F = {H}$ ，我们简单地说G是H-free的。如果 $H = K_{1, 3}$ ，我们称 $K_{1, 3}$ -free为无爪图。我们将F中的图称为禁止子图。对于禁止子图的哈密尔顿性已经被广泛研究，见文献 [2] - [6] 。

1971年，Bondy在 [7] 中提出了一个有趣的猜想(meta-conjecture)：几乎任何对图的非平凡条件，若暗示图是哈密尔顿的(Hamiltonian)，那么也意味着图是泛圈的(可能存在反例)。近50年来，这一猜想得到扩展，M. Cream，R.J. Gould和K. Hirohata认为几乎任何暗示图为哈密尔顿图的条件也意味着图是弦泛圈图，可能会有一类明确定义的反例图和一些顶点较少的反例图。下面几个定理进一步支持了Bondy经典猜想的扩展。

对于图G和H，令 $G □ H$ 表示G和H的笛卡尔积。

定理1.1. [8] 设G是阶数为 $n (n \geq 4)$ 的图。如果对于G中任意一对不相邻的顶点x和y的度和 $d (x) + d (y) \geq n$ ，那么G是弦泛圈的，或者 $G = K_{n / 2, n / 2}$ ，或者 $G = K_{3} □ K_{2}$ 。

定理1.2. [9] 一个阶数为 $n (n \geq 4)$ 的哈密尔顿图G，如果其边数 $| E (G) | \geq \frac{n^{2}}{4}$ ，则G是弦泛圈的，或者 $G = K_{n / 2, n / 2}$ ，或者 $G = K_{3} □ K_{2}$ 。

定理1.3. [10] 设G是阶数为 $n (n \geq 35)$ 的2-连通无爪图，如果 $δ (G) \geq \frac{n - 2}{3}$ ，则G是弦泛圈图。

我们研究了 $K_{1, 3}$ -free图形成弦泛圈图的邻域条件。下面所给的结论启发了我们的研究。该结果给出了 $K_{1, 3}$ -free图形成泛圈图的邻域条件。

定理1.4. [11] 令G是阶数为 $n (n \geq 14)$ 的2-连通无爪图。如果对于G中每一对不相邻的顶点u和v，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3}$ ，则G是泛圈的。

根据定理1.4与Bondy猜想的扩展，我们将泛圈性扩展为弦泛圈性，具体结果如下：

定理1.5. 令G是阶数为 $n (n \geq 43)$ 的2-连通无爪图。如果对G中每一对不相邻的顶点u和v，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3}$ ，则G是弦泛圈的。

在本文中，第一部分介绍了相关的符号定义以及定理，第二部分给出了证明过程所需要的重要引理，第三部分进行主要结果的证明，第四部分进行了本文总结以及后续研究的展望。接下来，我们给出了证明所需的重要引理。

2. 引理

为了证明主要结果，我们介绍以下引理：

定理2.1. [12] 令G是一个阶数为 $n (n \geq 3)$ 的图。如果对于某个s，G是s-连通的，并且不包含超过s个顶点的独立集，则G是哈密尔顿圈。

根据定理2.1，我们得到下面的引理：

引理2.2. 设G是一个无爪图。对于任意的 $x \in V (G)$ ， $G [N_{G} (x)]$ 要么是可追踪的，要么是两个不相交的团。

证明：假设x是G的任意顶点。由于G是 $K_{1, 3}$ -free的，根据定理2.1，如果 $G [N_{G} (x)]$ 是连通的，则 $G [N_{G} (x)]$ 是可追踪的。假设 $G [N_{G} (x)]$ 是不连通的，那么由于G是 $K_{1, 3}$ -free的， $G [N_{G} (x)]$ 中只有两个分支G₁和G₂。不失一般性，假设G₁中存在一对不相邻的顶点u和v，设z是G₂中的一个顶点。那么 ${x, u, v, z}$ 在G中导出一个 $K_{1, 3}$ ，这与G是 $K_{1, 3}$ -free的相矛盾。因此， $G [N_{G} (x)]$ 是两个不相交的团。该引理的证明完成。

3. 主要结果的证明

接下来我们将证明定理1.5。

证明：对于任意一对不相邻的顶点u和v，由于 $n \geq 43$ ，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3} \geq 28$ 。利用反证法，假设G不是弦泛圈的。设m是一个最大的值，满足 $4 \leq m \leq n$ ，使得G中长度为m的每个圈都没有弦。根据定理1.4，存在一个长度为n的弦圈，因此 $m \neq n$ 。令 $R = G - C_{m}$ ，根据定理1.4，G必然是泛圈的。根据m的值将证明分为以下几种情况。

情况1. $m \geq 9$ 。

设 $C_{m} = v_{1} v_{2} v_{3} \dots v_{m} v_{1}$ 是G中长度为m的圈。由于 $C_{m}$ 没有弦，那么 ${v_{1}, v_{4}, v_{7}}$ 是一个独立集。

假设 $N_{R} (v_{1}) \cap N_{R} (v_{4}) \neq \emptyset$ ，令 $a \in N_{R} (v_{1}) \cap N_{R} (v_{4})$ 。假设对于 $5 \leq i \leq m$ ，有 $N_{R - {a}} (v_{i}) \neq \emptyset$ ，令 $b \in N_{R - {a}} (v_{i})$ 。由于G是 $K_{1, 3}$ -free的，并且G没有长度为m的弦圈，因此 $v_{i - 1} b \in E (G)$ 或 $v_{i + 1} b \in E (G)$ 。如果 $v_{i - 1} b \in E (G)$ ，则 $C_{m} = v_{1} a v_{4} \dots v_{i - 1} b v_{i} \dots v_{m} v_{1}$ ；如果 $v_{i + 1} b \in E (G)$ ，则 $C = v_{1} a v_{4} \dots v_{i} b v_{i + 1} \dots v_{m} v_{1}$ 。在这两种情况下，C都是长度为m且有弦 $v_{i - 1} v_{i}$ 和 $v_{i} v_{i + 1}$ 的圈，这与假设矛盾。因此， $N_{R - {a}} (v_{i}) = \emptyset$ 。由于G没有长度为m的弦圈， $| N (v_{5}) \cup N (v_{7}) | \leq 4$ ，这与 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3} \geq 28$ 相矛盾。因此， $N_{R} (v_{1}) \cap N_{R} (v_{4}) \neq \emptyset$ 。同理， $N_{R} (v_{4}) \cap N_{R} (v_{7}) = \emptyset$ 。

情况1.1. $m = 9$ 。

根据 $N_{R} (v_{1}) \cap N_{R} (v_{4}) = \emptyset$ ，可得 $N_{R} (v_{1}) \cap N_{R} (v_{7}) = \emptyset$ 。由于G中长度为m的每个圈都没有弦，所以 $| N_{C_{9}} (v_{1}) \cup N_{C_{9}} (v_{4}) | + | N_{C_{9}} (v_{4}) \cup N_{C_{9}} (v_{7}) | + | N_{C_{9}} (v_{1}) \cup N_{C_{9}} (v_{7}) | \leq 12$ ，因此可以得到以下不等式：

$\begin{matrix} 3 \times \frac{2 n - 2}{3} \leq | N (v_{1}) \cup N (v_{4}) | + | N (v_{4}) \cup N (v_{7}) | + | N (v_{1}) \cup N (v_{7}) | \\ = 12 + | N_{R} (v_{1}) \cup N_{R} (v_{4}) | + | N_{R} (v_{4}) \cup N_{R} (v_{7}) | + | N_{R} (v_{1}) \cup N_{R} (v_{7}) | \\ = 12 + 2 (| N_{R} (v_{1}) | + | N_{R} (v_{4}) | + | N_{R} (v_{7}) |) \\ \leq 12 + 2 | R | \leq 2 n - 6 \end{matrix}$

得矛盾。

情况1.2. $m \geq 10$ 。

假设 $| N_{R} (v_{1}) \cap N_{R} (v_{7}) | \geq 3$ 。令 $x_{1}, x_{2}, x_{3}$ 是 $N_{R} (v_{1}) \cap N_{R} (v_{7})$ 中的不同顶点。由于G是 $K_{1, 3}$ -free图，不妨假设 $x_{1} x_{2} \in E (G)$ 。由于 $| N (v_{8}) \cup N (v_{10}) | \geq \frac{2 n - 2}{3} \geq 28$ ，那么至少有三个顶点 $y_{1}, y_{2}, y_{3}$ 满足 $y_{1}, y_{2}, y_{3} \in N_{R - {x_{1}, x_{2}}} (v_{8})$ 或者 $y_{1}, y_{2}, y_{3} \in N_{R - {x_{1}, x_{2}}} (v_{10})$ 。

由此在G中构造一个长度为m弦圈。令 $y_{1}, y_{2}, y_{3} \in N (v_{8})$ ，由于G是 $K_{1, 3}$ -free图，我们可以假设 $y_{1} y_{2} \in E (G)$ 。由于 $C_{m}$ 没有弦，且G是 $K_{1, 3}$ -free图，所以y₁和y₃要么与v₇相邻，要么与v₉相邻。假设v₇和v₉中有一个点不与y₁或y₃相邻。那么由于G是 $K_{1, 3}$ -free 图， $y_{1} y_{3} \in E (G)$ 。如果 $y_{1} v_{7} \in E (G)$ 且v₉与y₁和y₃不相邻，从而 $G [{v_{8}, v_{7}, v_{9}, y_{3}}]$ 导出一个 $K_{1, 3}$ ，则 $y_{3} v_{7} \in E (G)$ ，则存在 $C = v_{1} x_{1} x_{2} v_{7} y_{3} y_{1} y_{2} v_{8} v_{9} \dots v_{m} v_{1}$ ；如果 $y_{1} v_{9} \in E (G)$ 且v₇与y₁和y₃不相邻，同理， $y_{3} v_{9} \in E (G)$ ，则存在 $C = v_{1} x_{1} x_{2} v_{7} v_{8} y_{2} y_{1} y_{3} v_{9} \dots v_{m} v_{1}$ 。在这两种情况中，C是长度为m的弦圈，与假设矛盾。因此v₇和v₉都与y₁或y₃相邻。如果 $y_{1} v_{7} \in E (G)$ ， $y_{3} v_{9} \in E (G)$ ，则 $C^{'} = v_{1} x_{1} x_{2} v_{7} y_{1} y_{2} v_{8} y_{3} v_{9} \dots v_{m} v_{1}$ ；如果 $y_{3} v_{7} \in E (G)$ ， $y_{1} v_{9} \in E (G)$ ，则 $C^{'} = v_{1} x_{1} x_{2} v_{7} y_{3} v_{8} y_{2} y_{1} v_{9} \dots v_{m} v_{1}$ 。在这两种情况下， $C^{'}$ 是长度为m的弦圈，与假设矛盾。

同理，假设 $y_{1}, y_{2}, y_{3} \in N (v_{10})$ ，则可得到一个长度为m的弦圈。因此， $| N_{R} (v_{1}) \cap N_{R} (v_{7}) | \leq 2$ 。因此存在以下不等式：

$\begin{matrix} 3 \times \frac{2 n - 2}{3} \leq | N (v_{1}) \cap N (v_{4}) | + | N (v_{4}) \cap N (v_{7}) | + | N (v_{1}) \cap N (v_{7}) | \\ \leq 12 + | N_{R} (v_{1}) \cap N_{R} (v_{4}) | + | N_{R} (v_{4}) \cap N_{R} (v_{4}) | + | N_{R} (v_{1}) \cap N_{R} (v_{7}) | \\ \leq 12 + 2 (| N_{R} (v_{1}) | + | N_{R} (v_{4}) | + | N_{R} (v_{7}) |) \\ \leq 12 + 2 (| R | + 2) \leq 2 n - 4 \end{matrix}$

得矛盾，情况1得证。

情况2. $4 \leq m \leq 8$ 。

如果G是一个完全图，那么我们证明就完成了。如果存在两个不相邻的顶点 $u, v \in V (G)$ ，那么 $| N (u) | \geq 14$ 或 $| N (v) | \geq 14$ ，因为 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3} \geq 28$ 。不失一般性，我们假设 $| N (u) | \geq 14$ 。根据引理2.2， $G [N (u)]$ 是可追踪的或两个不相交的团。如果 $G [N (u)]$ 是可追踪的，那么必定存在一个长度为 $k (4 \leq k \leq 8)$ 的弦圈。如果 $G [N (u)]$ 是两个不相交的团G₁和G₂，那么 $| G_{1} | \geq 7$ 或 $| G_{2} | \geq 7$ ，并且必定存在一个长度为 $k (4 \leq k \leq 8)$ 的弦圈，情况2得证。

综上所述，令G是阶数为 $n (n \geq 43)$ 的2-连通无爪图。如果对G中每一对不相邻的顶点 $u, v$ ，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3}$ ，则G是弦泛圈的。

4. 总结与展望

在本文中，我们利用反证法证明了2-连通无爪图形成弦泛圈图的领域条件，即令G是阶数为 $n (n \geq 43)$ 的2-连通无爪图。如果对G中每一对不相邻的顶点u和v，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3}$ ，则是弦泛圈图，这是对Bondy猜想拓展的一个验证。在这个结论下，我们可以进行进一步的研究，证明其双弦泛圈性，以及计算弦的个数，具体猜想与问题如下。

如果一个圈至少有两条弦，则称该圈为双弦圈(doubly Chorded Cycle)。如果一个阶数为n的图G包含每个长度从4到n的双弦圈，则称该图为双弦泛圈的(doubly Chorded Pancyclic)。根据所得的结果，我们有进一步的猜想：

猜想4.1. 令G是阶数为 $n (n \geq 43)$ 的2-连通无爪图，如果对于G中任意一对不相邻的顶点 $u, v$ ，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3}$ ，则G是双弦泛圈的。

问题4.2. 令G是阶数为 $n (n \geq 43)$ 的2-连通无爪图，如果对G中任意一对不相邻的顶点 $u, v$ ，有 $| N (u) \cup N (v) | \geq \frac{2 n - 2}{3}$ ，则G含有多少条弦？怎样计算每个弦圈中含有弦的个数？

基金项目

四川国家应用数学中心–成都信息工程大学智能系统应用数学研究所项目基金(2023ZX003)和科学研究项目基金(KYTZ2022146)。

参考文献

[1]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London. https://doi.org/10.1007/978-1-349-03521-2
[2]	Faudree, R.J. and Gould, R.J. (1997) Characterizing Forbidden Pairs for Hamiltonian Properties. Discrete Mathematics, 273, 45-60. https://doi.org/10.1016/S0012-365X(96)00147-1
[3]	Gould, R.J. and Jacobson, M.S. (1982) Forbidden Subgraphs and Hamiltonian Properties of Graphs. Discrete Mathematics, 42, 189-196. https://doi.org/10.1016/0012-365X(82)90216-3
[4]	Brousek, J., Ryjáček, Z. and Schiermeyer, I. (1999) Forbidden Subgraphs, Stability and Hamiltonicity. Discrete Mathematics, 197, 143-155.
[5]	Faudree, R., Gould, R. and Jacobson, M. (2004) Forbidden Triples Implying Hamiltonicity: For All Graphs. Discussiones Mathematicae Graph Theory, 24, 47-54. https://doi.org/10.7151/dmgt.1212
[6]	Bedrossian, P.M. (1991) Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity. Ph.D. Thesis, Memphis State University, Memphis.
[7]	Bondy, J.A. (1971) Pancyclic Graphs I. Journal of Combinatorial Theory, Series B, 11, 80-84. https://doi.org/10.1016/0095-8956(71)90016-5
[8]	Cream, M., Gould, R.J. and Hirohata, K. (2017) A Note on Extending Bondy’s Meta-Conjecture. The Australasian Journal of Combinatorics, 67, 463-469.
[9]	Chen, G., Gould, R.J., Gu, X.F. and Saito, A. (2018) Cycles with a Chord in Dense Graphs. Discrete Mathematics, 342, 2131-2142. https://doi.org/10.1016/j.disc.2018.04.016
[10]	Tian, Z.X. (2021) Pancyclicity in Hamiltonian Graph Theory. Ph.D. Thesis, Université Paris-Saclay, Paris.
[11]	Faudree, R.J., Gould, R.J. and Lindquester, T.E. (1991) Hamiltonian Properties and Adjacency Conditions in-Free Graphs. Graph Theory Combinatorics and Applications, 1, 467-479.
[12]	Chvátal, V. and Erdös, P. (1972) A Note on Hmiltonian Circuits. Discrete Mathematics, 2, 111-113. https://doi.org/10.1016/0012-365X(72)90079-9

为你推荐

友情链接