K 1,3 -Free图上的弦泛圈性 Chorded Pancyclicity on K 1,3 -Free Graph

doi:10.12677/aam.2024.135187

Advances in Applied Mathematics
Vol. 13 No. 05 ( 2024 ), Article ID: 87252 , 6 pages
10.12677/aam.2024.135187

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

李欢¹，田增娴²，杨卫华^1*

●How to Cite this Article

¹太原理工大学数学学院，山西太原

²成都信息工程大学应用数学学院，四川成都

收稿日期：2024年4月21日；录用日期：2024年5月14日；发布日期：2024年5月23日

摘要

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

关键词

$K_{1, 3}$ -Free，弦圈，泛圈，弦泛圈，哈密尔顿

Chorded Pancyclicity on $K_{1, 3}$ -Free Graph

Huan Li¹, Zengxian Tian², Weihua Yang^1*

¹School of Mathematics, Taiyuan University of Technology, Taiyuan Shanxi

²College of Applied Mathematics, Chengdu University of Information Technology, Chengdu Sichuan

Received: Apr. 21^st, 2024; accepted: May 14^th, 2024; published: May 23^rd, 2024

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-connected $K_{1, 3}$ -free graph with the order $n (n \geq 14)$ . If $| N (x) \cup N (y) | \geq \frac{2 n - 2}{3}$ for each pair of nonadjacent vertices $x, y$ , then G is pancyclic. In this paper, we extended this result by generalizing the concept of pancyclicto chorded pancyclic: ever 2-connected, $K_{1, 3}$ -free graph G with order $n \geq 43$ is chorded pancyclic if the number of the union of for each pair of nonadjacent vertices at least $\frac{2 n - 2}{3}$ .

Keywords: $K_{1, 3}$ -Free, Chorded Cycle, Pancyclic, Chorded Pancyclic, Hamiltonian

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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)。

文章引用

李欢,田增娴,杨卫华. $K_{1, 3}$ -Free图上的弦泛圈性
Chorded Pancyclicity on $K_{1, 3}$ -Free Graph[J]. 应用数学进展, 2024, 13(05): 1994-1999. https://doi.org/10.12677/aam.2024.135187

参考文献

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

期刊菜单