玫瑰花窗图R3k(1,3)的交叉数

doi:10.12677/AAM.2024.132063

期刊菜单

玫瑰花窗图R_3k(1,3)的交叉数
The Crossing Number of Rose Windows Graph R_3k(1,3)

DOI: 10.12677/AAM.2024.132063, PDF, HTML, XML, 下载: 39 浏览: 68
作者: 张瑜洁：辽宁师范大学数学学院，辽宁大连
关键词: 玫瑰花窗图；交叉数；好画法；Rose Windows Graph； Crossing Number； Good Drawing

摘要: 图的交叉数是图论中一个重要的部分。近百年来，国内外很多学者都对图的交叉数这一问题进行研究，但由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。本文主要对玫瑰花窗图R_3k(1,3)的交叉数进行研究。首先根据好的画法得到R_3k(1,3)的交叉数上界；再将R_3k(1,3)的边集分成边不相交的3k组，利用反证法和数学归纳法，讨论所有可能情况，证得R_3k(1,3)的交叉数下界至少是2k，从而得到cr(R_3k(1,3))≥2k，k≥3。

Abstract: Crossing number of graphs is an important part of graph theory, and many scholars at home and abroad have studied the problem of crossing number of graphs in the past hundred years, but due to the difficulty of proving it, the progress of domestic and foreign research on the field of crossing number of graphs has been slow. This paper focuses on the study of the crossing number of rose window graphs R_3k(1,3) . Firstly, we get the upper bound of the crossover number of R_3k(1,3) based on the well-drawn method; then divide the set of edges of R_3k(1,3) into the 3k groups whose edges do not intersect, and using the inverse method and the mathematical induction method, all possible cases are discussed, so that we can prove that the lower bound of the crossover number of R_3k(1,3) is at least 2k, and thus we can prove that cr(R_3k(1,3))≥2k , k≥3 .

文章引用：张瑜洁. 玫瑰花窗图R_3k(1,3)的交叉数[J]. 应用数学进展, 2024, 13(2): 653-660. https://doi.org/10.12677/AAM.2024.132063

1. 引言

图的交叉数是图论中一个重要的部分。近百年来，国内外很多学者都对图的交叉数这一问题进行研究。图的交叉数问题的研究，起源于20世纪40年代砖厂遇到的难题。第二次世界大战时期，Turan [1] 发现运砖车沿铁轨向仓库运砖时，车很容易在铁轨交点的位置脱节。他因此想到通过减少铁轨交叉个数来降低损失的方法，交叉数的概念由此而来。研究图的交叉数是一项富有意义但充满挑战性的工作。其实，在1983年，Garey和Johnson [2] 已经证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。下面主要介绍广义Petersen图的研究成果。

广义Petersen图

最早研究广义Petersen图在1981年，Exoo C，Harary和Kabel [3] 对图的交叉数进行研究，得出：

${\begin{cases} c r (P (3 h, 3)) = h, h \geq 4, \\ c r (P (3 h + 1, 3)) \geq h + 3, h \geq 3, \\ c r (P (3 h + 2, 3)) = h + 2, h \geq 2. \end{cases}$

1986年Fiorini [4] 给出广义Petersen图 $P (n, 3)$ 的交叉数的证明，但是，Richter和Salazar [5] 随后指出其证明存在错误，他们证明广义Petersen图 $P (n, 3)$ 的交叉数为：

${\begin{cases} c r (P (3 h, 3)) = h, h \geq 4, \\ c r (P (3 h + 1, 3)) \geq h + 3, h \geq 3, \\ c r (P (3 h + 2, 3)) = h + 2, h \geq 2. \end{cases}$

2004年，林晓惠 [6] 得出了 $P (4 k + 2, 2 k)$ 等部分广义Petersen图的交叉数的上界；2005年，马登举等人证明了 $G (2 m + 1, m)$ 的交叉数 [7] ；2009年，杨元生等人利用算法给出了 $n \geq 16$ 时 $P (n, k)$ 的交叉数的精确值 [8] ；Fiorinil和黄元秋等人分别用不同方法证明了 $P (3 k, k)$ 的交叉数 [9] ；2013年，郑百功证明了 $P (10, 3)$ 的交叉数 [10] 。2019年，Gauci和Xuereb [11] 证明了当 $k \geq 3$ 时有：

$c r (G P (3 k - 1, k)) = k + 1,$

$c r (G P (3 k + 1, k)) = k + 3.$

2020年，历莹 [12] 通过研究 $P (12, 5)$ 的子图的性质，证明得出 $P (12, 5)$ 的交叉数的下界至少是6，进而提出猜想：当 $k \geq 5$ 时， $c r (P (2 k + 2, k)) \geq k + 1$ 。2023年，卢妮 [13] 证明了Chimani的猜想：当 $k \geq 5$ 时，有 $c r (P (4 k, 4)) = 2 k$ 。2023年，白贺 [14] 在其硕士论文中证明了双广义Petersen图的交叉数 $c r (D P (7, 1)) = 7$ 。

2. 玫瑰花窗图 $R_{3 k} (1, 3)$ 的定义

为方便书写，下文将玫瑰花窗图 $R_{3 k} (1, 3)$ 记作 $R_{3 k} (1, 3)$ ，其中 $k \geq 3$ 。设 $R_{3 k} (1, 3)$ 的顶点集为 $V (R_{3 k} (1, 3)) = {a_{i}, b_{i} : 1 \leq i \leq 3 k}$ ，边集为 $E (R_{3 k} (1, 3)) = {a_{i} a_{i + 1}, a_{i} b_{i}, b_{i} b_{i + 3}, b_{i} a_{i + 1} : 1 \leq i \leq 3 k}$ ，其中下标取模3k。

设G是一个简单图。G的一个分解是G的边不相交子图的列表，使得G的每条边都出现在列表中的一个子图中。如果对于每对整数i和j， $1 \leq i, j \leq t$ ，G存在一个自同构 $θ_{i, j}$ ，使得 $u v \in E (H_{i + l})$ 当且仅当 $θ_{i, j} (u) θ_{i, j} (v) \in E (H_{j + l})$ ，则称图G的一个分解 ${H_{1}, H_{2}, \dots, H_{t}}$ 是可传递的，其中下标取t的模。如果存在图G的一个传递分解，则称图G是广义周期图。

设 $V (T_{i}) = {a_{i}, b_{i}, a_{i + 1} : 1 \leq i \leq 3 k}$ ，且 $T_{i}$ 为三角形 $a_{i} b_{i} a_{i + 1} a_{i}$ 。设 $B_{i}$ 为领结图 $T_{i - 1} \cup T_{i}$ ， $1 \leq i \leq 3 k$ 。设 $E_{i}$ 的顶点集为 $V (E_{i}) = V (T_{i}) \cup {b_{i + 3}}$ ，边集为 $E (E_{i}) = E (T_{i}) \cup {b_{i} b_{i + 3}}$ ， $1 \leq i \leq 3 k$ 。显然 ${E_{1}, E_{2}, \dots, E_{3 k}}$ 是 $R_{3 k} (1, 3)$ 的一个可传递分解，其中 $k \geq 3$ 。因此 $R_{3 k} (1, 3)$ 是一个广义周期图。设 $V (H_{i}) = V (E_{i}) \cup {a_{i + 2}, a_{i + 3}}$ 且 $E (H_{i}) = E (E_{i}) \cup {a_{i + 1} a_{i + 2}, a_{i + 2} a_{i + 3}, a_{i + 3} b_{i + 3}}$ ， $1 \leq i \leq 3 k$ 。

对于图G，设H是G的子图且 $f_{D} (H)$ 是H到所有非负实数集合的映射：

$f_{D} (H) = c r_{D} (H) + c r_{D} (H, G \ E (H)) / 2$ .

Jordan曲线定理任意一条简单(自身不相交)闭曲线J把平面分成两个区域，在不同区域的两点若要相连，则连结的弧必与J相交。

根据Jordan曲线定理，我们有以下引理：

引理2.1 在图G中，设C和C'为两个顶点不相交的圈， $P_{k} = u_{1} u_{2} \dots u_{k}$ 为k阶路径且 $V (P_{k}) \cap V (C) = \emptyset$ 。假设D是G的一个好画法，则 $c r_{D} (C, C^{'})$ 为偶数；当 $u_{1}$ 和 $u_{k}$ 在 $D (C)$ 的同一区域时，为偶数，否则为奇数。

引理2.2 设c是一个正整数，对于 $1 \leq i \leq t$ ，若存在一个正整数 $l_{i}$ 满足 $f_{D} (H_{i, i - 1 + l_{i}}) \geq l_{i} c$ ，则令 $L_{i}^{D}$ 为 $l_{i}$ 的最小值使 $f_{D} (H_{i, i - 1 + l_{i}}) \geq l_{i} c$ ；若不存在这样的正整数 $l_{i}$ ，则令 $L_{i}^{D} = + \infty$ 。

3. 玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数

3.1. 玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数的上界

引理3.1 $c r (R_{9} (1, 3)) = 6$ 。

引理3.2 对于 $k \geq 3$ ， $c r (R_{3 k} (1, 3)) \leq 2 k$ 。

证明：如图1所示，给出了 $R_{3 k} (1, 3)$ 的一个只有2k个交叉数的好画法。因此，当 $k \geq 3$ 时， $c r (R_{3 k} (1, 3)) \leq 2 k$ 。

3.2. 玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数的下界

引理3.3 (领结引理) 设 $1 \leq i \leq 3 k$ ，D是 $B_{i}$ 的一个好画法且 $c r_{D} (B_{i}) = 1$ 。则 $a_{i + 1}$ 和 $b_{i}$ 被 $D (T_{i - 1})$ 分离或 $a_{i - 1}$ 和 $b_{i - 1}$ 被 $D (T_{i})$ 分离。

证明：假设 $a_{i + 1}$ 和 $b_{i}$ 在 $D (T_{i - 1})$ 划分平面的同一区域。若 $c r_{D} (a_{i + 1} b_{i}, T_{i - 1}) \geq 1$ ，由引理2.1， $c r_{D} (a_{i + 1} b_{i}, T_{i - 1}) \geq 2$ ，这与 $c r_{D} (B_{i}) = 1$ 矛盾。因此 $c r_{D} (a_{i + 1} b_{i}, T_{i - 1}) = 0$ 。由 $c r_{D} (B_{i}) = 1$ 知 $c r_{D} (b_{i} a_{i} a_{i + 1}, T_{i - 1}) = 1$ 。又由于D是好的画法，所以 $c r_{D} (a_{i - 1} b_{i - 1}, b_{i} a_{i} a_{i + 1}) = 1$ 。因此， $a_{i - 1}$ 和 $b_{i - 1}$ 被 $D (T_{i})$ 分离。

Figure 1. A good drawing of with 2k crossings

图1. 有2k个交叉点的好的画法

引理3.4 设D是 $R_{3 k} (1, 3)$ 的一个好画法且 $c r (R_{3 k} (1, 3)) < 2 k$ ， $k \geq 3$ 。若 $l_{1}^{D} \geq 4$ ，那么 $c r_{D} (B_{3}, E_{1}) = 0$ ； $c r_{D} (B_{i}) = 0$ ， $2 \leq i \leq 3$ ； $c r_{D} (T_{1}, T_{j}) = 0$ ， $3 \leq j \leq 3 k$ 。

证明：由 $l_{1}^{D} \geq 4$ ，有 $f_{D} (E_{1}) < \frac{2}{3}$ ， $f_{D} (E_{1, 2}) < 4 / 3$ ， $f_{D} (E_{1, 3}) < 2$ 。反证法。假设 $c r_{D} (T_{1}, T_{j}) \geq 1$ ， $3 \leq j \leq 3 k$ 。由引理2.1可知 $c r_{D} (T_{1}, T_{j}) \geq 2$ ，与 $f_{D} (E_{1}) < 2 / 3$ 相矛盾。因此 $c r_{D} (T_{1}, T_{j}) = 0$ ， $3 \leq j \leq 3 k$ 。

假设 $c r_{D} (B_{2}) \geq 1$ 。由 $f_{D} (E_{1, 2}) < \frac{4}{3}$ ，有 $c r_{D} (B_{2}) = 1$ 。根据引理3.3， $a_{3}$ 和 $b_{2}$ 被 $D (T_{1})$ 分离或 $a_{1}$ 和 $b_{1}$ 被 $D (T_{2})$ 分离。由引理2.1，若 $a_{3}$ 和 $b_{2}$ 被 $D (T_{1})$ 分离，路径 $a_{3} a_{4} a_{5} b_{5} b_{2}$ 与 $T_{1}$ 相交；若 $a_{1}$ 和 $b_{1}$ 被 $D (T_{2})$ 分离，路径 $b_{1} b_{3 k - 2} a_{3 k - 1} a_{3 k} a_{1}$ 与 $T_{2}$ 相交。两种情形均有 $f_{D} (E_{1, 2}) \geq \frac{4}{3}$ ，矛盾。因此 $c r_{D} (B_{2}) = 0$ 。

假设 $c r_{D} (B_{3}) \geq 1$ 。由 $f_{D} (E_{1, 3}) < 2$ ，有 $c r_{D} (B_{3}) = 1$ 。根据引理3.3， $a_{4}$ 和 $b_{3}$ 被 $D (T_{2})$ 分离或 $a_{2}$ 和 $b_{2}$ 被 $D (T_{3})$ 分离。由引理2.1，若 $a_{4}$ 和 $b_{3}$ 被 $D (T_{2})$ 分离，路径 $b_{3} b_{6} a_{6} a_{5} a_{4}$ 和 $b_{3} b_{3 k} a_{3 k} a_{3 k - 1} b_{3 k - 2} P_{1} b_{4} a_{4}$ 与 $T_{2}$ 相交；若 $a_{2}$ 和 $b_{2}$ 被 $D (T_{3})$ 分离，路径 $b_{2} b_{5} a_{6} b_{6} P_{3} b_{3 k} a_{1}$ 和 $b_{2} b_{3 k - 1} a_{3 k - 1} a_{3 k} a_{1}$ 与 $T_{3}$ 相交。两种情形均有 $f_{D} (E_{1, 3}) \geq 2$ ，矛盾。因此 $c r_{D} (B_{3}) = 0$ 。

假设 $c r_{D} (B_{3}, E_{1}) = 1$ ，则有 $c r_{D} (T_{2}, E_{1}) \geq 1$ 或 $c r_{D} (T_{3}, E_{1}) \geq 1$ 。假设 $c r_{D} (T_{2}, E_{1}) \geq 1$ 。由 $f_{D} (E_{1, 2}) < \frac{4}{3}$ ，有 $c r_{D} (T_{2}, E_{1}) = 1$ 。根据 $c r_{D} (B_{2}) = 0$ 知 $c r_{D} (b_{1} b_{4}, T_{2}) = 1$ . 由引理2.1， $b_{1}$ 和 $b_{4}$ 被 $D (T_{2})$ 分离且路径 $b_{1} b_{3 k - 2} P_{1} b_{4}$ 交 $T_{2}$ ，则 $f_{D} (E_{1, 2}) \geq \frac{4}{3}$ ，矛盾。因此 $c r_{D} (T_{2}, E_{1}) = 0$ . 假设 $c r_{D} (T_{3}, E_{1}) \geq 1$ 。由 $c r_{D} (T_{1}, T_{3}) = 0$ 及 $f_{D} (E_{1}) < \frac{2}{3}$ ，有 $c r_{D} (b_{1} b_{4}, T_{3}) = 1$ 。根据引理2.1， $b_{1}$ 和 $b_{4}$ 被 $D (T_{3})$ 分离，且由 $c r_{D} (T_{1}, T_{3}) = 0$ 有 $a_{1}$ 和 $b_{4}$ 被 $D (T_{3})$ 分离。由引理2.1，路径 $a_{1} b_{3 k} b_{3} a_{3} a_{4} a_{5} b_{4}$ 和 $a_{1} P_{0} a_{8} b_{7} b_{4}$ 与 $T_{3}$ 相交，与 $f_{D} (E_{1, 3}) < 2$ 矛盾。因此 $c r_{D} (T_{3}, b_{1} b_{4}) = 1$ 。即 $c r_{D} (T_{3}, E_{1}) = 0$ 。由于 $c r_{D} (T_{2}, E_{1}) = 0$ ，因此 $c r_{D} (B_{3}, E_{1}) = 0$ 。

引理3.5 (画法引理) 设D是 $R_{3 k} (1, 3)$ 的一个好画法使得 $c r (R_{3 k} (1, 3)) < 2 k$ ，且 $c r (R_{3 (k - 1)} (1, 3)) \geq 2 (k - 1)$ ， $k \geq 3$ 。若路径 $a_{i} b_{i} a_{i + 1} b_{i + 1} a_{i + 2} b_{i + 2} a_{i + 3}$ 上有m个交叉点，则路径 $a_{i} a_{i + 1} a_{i + 2} a_{i + 3}$ 上至少有 $m - 1$ 个交叉点；若路径 $b_{i} a_{i + 1} b_{i + 1} a_{i + 2} b_{i + 2} a_{i + 3} b_{i + 3}$ 上有m个交叉点，则路径 $b_{i} b_{i + 3}$ 上至少有 $m - 1$ 个交叉点。其中 $m \geq 2$ ， $1 \leq i \leq 3 k$ 。

引理3.6 设D是 $R_{3 k} (1, 3)$ 的一个好画法使得 $c r (R_{3 k} (1, 3)) < 2 k$ ，且 $c r (R_{3 (k - 1)} (1, 3)) \geq 2 (k - 1)$ ， $k \geq 3$ 。若 $l_{1}^{D} \geq 5$ ，则 $D (H_{1})$ 同构于图3。

子情形一： $b_{2}$ 在区域 $R_{2}$ 。

证明：通过 $l_{1}^{D} \geq 5$ ，得到 $f_{D} (E_{1}) < \frac{2}{3}$ ， $f_{D} (E_{1, 2}) < \frac{4}{3}$ ， $f_{D} (E_{1, 3}) < 2$ ， $f_{D} (E_{1, 4}) < \frac{8}{3}$ 。由引理3.4知， $c r_{D} (B_{3}, E_{1}) = 0$ ， $c r_{D} (T_{1}, T_{j}) = 0$ ， $3 \leq j \leq 3 k$ ，即有 $c r_{D} (E_{1}, a_{2} a_{3} a_{4} b_{4}) = 0$ 。再根据好的画法的定义，有 $c r_{D} (a_{2} a_{3}, a_{4} b_{4}) \leq 1$ 。当 $c r_{D} (a_{2} a_{3}, a_{4} b_{4}) = 1$ 时， $D (H_{1})$ 同构于图2(a)或图2(b)。

由于 $c r_{D} (a_{2} a_{3}, a_{4} b_{4}) = 1$ ，根据引理2.1， $c r_{D} (T_{2}, T_{4}) \geq 2$ 。若 $D (H_{1})$ 同构于图2(a)，由引理2.1，路径 $a_{1} b_{3 k} b_{3} a_{3}$ 和 $a_{1} a_{3 k} b_{3 k - 1} P_{2} b_{2} a_{3}$ 与 $H_{1}$ 相交，则 $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。若 $D (H_{1})$ 同构于图2(b)，由 $f_{D} (E_{1, 4}) < \frac{8}{3}$ 可知， $c r_{D} (a_{2} b_{2} a_{3}, a_{4} b_{4}) \leq 1$ 。若 $c r_{D} (a_{2} b_{2} a_{3}, a_{4} b_{4}) = 1$ ，由画法引理(引理3.5)可知， $a_{2} a_{3} a_{4} a_{5}$ 和 $b_{1} b_{4}$ 都不干净。因此， $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。故 $c r_{D} (a_{2} b_{2} a_{3}, a_{4} b_{4}) = 0$ ，即 $c r_{D} (a_{2} b_{2} a_{3}, H_{1}) = 0$ 。因此 $D (H_{1} \cup T_{2}) = 0$ 同构于图2(c)。由引理2.1，路径 $a_{1} b_{3 k} b_{3} a_{4}$ 和 $a_{1} a_{3 k} P_{0} a_{4}$ 与 $T_{2}$ 相交，则 $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。因此， $c r_{D} (a_{2} a_{3}, a_{4} b_{4}) = 0$ 。即 $c r_{D} (H_{1}) = 0$ 且 $D (H_{1})$ 同构于图3。

(a) (b) (c)

Figure 2. $D (H_{1})$ and $c r_{D} (H_{1}) = 1$

图2. $D (H_{1})$ 且 $c r_{D} (H_{1}) = 1$

Figure 3. $D (H_{1})$ and $c r_{D} (H_{1}) = 0$

图3. $D (H_{1})$ 且 $c r_{D} (H_{1}) = 0$

引理3.7 设D是 $R_{3 k} (1, 3)$ 的一个好画法且 $c r (R_{3 k} (1, 3)) < 2 k$ ， $k \geq 3$ 。若 $D (H_{1})$ 同构于图3， $b_{2}$ 在区域 $R_{2}$ 且 $l_{1}^{D} \geq 5$ ，则 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5。

证明：通过 $l_{1}^{D} \geq 5$ ，得到 $f_{D} (E_{1}) < \frac{2}{3}$ ， $f_{D} (E_{1, 2}) < \frac{4}{3}$ ， $f_{D} (E_{1, 3}) < 2$ ， $f_{D} (E_{1, 4}) < \frac{8}{3}$ 。由引理2.1，路径 $b_{2} b_{8} a_{9} P_{0} a_{3 k} a_{1}$ 和 $b_{2} b_{5} a_{6} b_{6} P_{3} a_{1}$ 交圈 $b_{4} b_{1} a_{2} a_{3} a_{4} b_{4}$ 。若 $c r_{D} (a_{4} b_{4}, T_{2}) \geq 1$ ，则由引理2.1可知 $c r_{D} (T_{2}, T_{4}) \geq 2$ 。因此， $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。故 $c r_{D} (a_{4} b_{4}, T_{2}) = 0$ 即 $c r_{D} (T_{2}, T_{4}) = 0$ 。根据引理3.4， $c r_{D} (T_{2}, E_{1}) = 0$ 且 $c r_{D} (B_{3}) = 0$ 。因此 $D (H_{1} \cup T_{2})$ 同构于图4(a)。

(a) (b)

Figure 4. The subdrawing of D

图4. D的子画法

由 $f_{D} (E_{1, 4}) < \frac{8}{3}$ 可知， $c r_{D} (B_{4}) \leq 1$ 。若 $c r_{D} (B_{4}) = 1$ ，根据引理3.3， $a_{3}$ 和 $b_{3}$ 被 $D (T_{4})$ 分离或 $a_{5}$ 和 $b_{4}$ 被 $D (T_{3})$ 分离。若 $a_{3}$ 和 $b_{3}$ 被 $D (T_{4})$ 分离，又由于 $c r_{D} (B_{3}) = 0$ 且 $c r_{D} (B_{3}, E_{1}) = 0$ ，则 $b_{1}$ 和 $b_{3}$ 位于 $D (T_{4})$ 划分平面的不同区域。由引理2.1，路径 $b_{1} b_{3 k - 2} P_{1} b_{7} a_{7} b_{6} b_{3}$ 与 $T_{4}$ 相交。由 $f_{D} (E_{1, 4}) < \frac{8}{3}$ 可知， $c r_{D} (b_{2} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 0$ 。因此 $b_{3}$ 和 $b_{5}$ 位于 $D (T_{4})$ 划分平面的不同区域。同理由引理2.1，路径 $b_{5} b_{8} a_{8} a_{9} b_{9} P_{4} b_{3 k} b_{3}$ 与 $T_{4}$ 相交。因此， $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。若 $a_{5}$ 和 $b_{4}$ 被 $D (T_{3})$ 分离，根据引理2.1，路径 $a_{5} a_{6} a_{7} b_{7} b_{4}$ 与 $T_{3}$ 相交。又由于 $c r_{D} (T_{3}, E_{1}) = 0$ ，同理由引理2.1，路径 $b_{1} b_{3 k - 2} P_{1} b_{7} a_{8} b_{8} b_{5} a_{5}$ 与 $T_{3}$ 相交。因此， $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。故 $c r_{D} (B_{4}) = 0$ 。若 $c r_{D} (b_{1} b_{4}, T_{4}) = 1$ 。根据好的画法有 $c r_{D} (b_{1} b_{4}, a_{4} a_{5}) = 1$ 且 $a_{5}$ 位于区域 $R_{2}$ 或 $R_{0}$ 。由引理2.1，路径 $b_{2} b_{8} a_{9} P_{0} a_{3 k} a_{1}$ 和 $b_{2} b_{5} a_{6} b_{6} P_{3} a_{1}$ 交圈 $b_{4} b_{1} a_{2} a_{3} a_{4} b_{4}$ 。根据 $f_{D} (E_{1, 2}) < \frac{4}{3}$ ，有 $c r_{D} (b_{2} b_{8} a_{9} P_{0} a_{3 k} a_{1} \cup b_{2} b_{5} a_{6} b_{6} P_{3} a_{1}, b_{4} b_{1} a_{2} a_{3}) \leq 1$ 。不失一般性，假设 $c r_{D} (b_{2} b_{8} a_{9} P_{0} a_{3 k} a_{1}, a_{3} a_{4} b_{4}) = 1$ 。根据引理3.4， $c r_{D} (B_{3}) = 0$ 且 $c r_{D} (T_{3}, T_{1}) = 0$ 。因此 $b_{2}$ 和 $a_{1}$ 位于 $D (T_{3})$ 划分平面的同一区域。同理，由 $c r_{D} (T_{4}, T_{1}) = 0$ 和 $c r_{D} (T_{2}, T_{4}) = 0$ 可知， $b_{2}$ 和 $a_{1}$ 位于 $D (T_{4})$ 划分平面的同一区域。根据引理2.1，若 $c r_{D} (b_{2} b_{8} a_{9} P_{0} a_{3 k} a_{1}, a_{3} a_{4} b_{4}) = 1$ ，则 $c r_{D} (b_{2} b_{8} a_{9} P_{0} a_{3 k} a_{1}, B_{4}) \geq 2$ 。当 $a_{5}$ 在区域 $R_{0}$ 时，由 $f_{D} (E_{1, 4}) < \frac{8}{3}$ 可知， $c r_{D} (b_{2} b_{5}, H_{1} \cup T_{2} \cup B_{4}) = 0$ ，因此 $b_{5}$ 位于区域 $R_{2}$ 或 $R_{3}$ 。这两种情形，由引理2.1均有路径 $a_{5} b_{5}$ 与 $H_{1} \cup T_{2} \cup B_{4}$ 相交。因此， $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。当 $a_{5}$ 在区域 $R_{2}$ 时， $D (H_{1} \cup T_{2} \cup T_{4})$ 同构于图4(b)。根据引理2.1可知，路径 $a_{5} P_{0} a_{3 k} a_{1}$ 和 $a_{5} b_{5} a_{6} b_{6} P_{3} b_{3 k} a_{1}$ 交圈 $b_{2} a_{2} b_{1} b_{4} a_{4} a_{3} b_{2}$ 。同理于上述情形， $c r_{D} (a_{5} P_{0} a_{3 k} a_{1} \cup a_{5} b_{5} a_{6} b_{6} P_{3} b_{3 k} a_{1}, b_{1} a_{2}) = 0$ ，且 $c r_{D} (a_{5} P_{0} a_{3 k} a_{1} \cup a_{5} b_{5} a_{6} b_{6} P_{3} b_{3 k} a_{1}, T_{2}) \geq 2$ ， $c r_{D} (a_{5} P_{0} a_{3 k} a_{1} \cup a_{5} b_{5} a_{6} b_{6} P_{3} b_{3 k} a_{1}, B_{4}) \geq 2$ 。因此， $f_{D} (E_{1, 4}) \geq \frac{8}{3}$ ，矛盾。故 $c r_{D} (b_{1} b_{4}, T_{4}) = 0$ 。 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5。

(a) (b) (c) (d)

Figure 5. $D (H_{1} \cup T_{2} \cup B_{4})$ and $b_{2}$ are in area $R_{2}$

图5. $D (H_{1} \cup T_{2} \cup B_{4})$ 且 $b_{2}$ 在区域 $R_{2}$

引理3.8 设D是 $R_{3 k} (1, 3)$ 的一个好画法使得 $c r (R_{3 k} (1, 3)) < 2 k$ ，且 $c r (R_{3 (k - 1)} (1, 3)) \geq 2 (k - 1)$ ， $k \geq 3$ 。若 $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5，则 $l_{1}^{D} \geq 5$ 。

情形1， $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(a)；

情形2， $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(b)或图5(c)；

情形3， $D (H_{1} \cup T_{2} \cup B_{4})$ 同构于图5(d)。

子情形二： $b_{2}$ 在区域 $R_{0}$ 。

通过上述证明，当 $k \geq 3$ 时，总有 $c r (R_{3 k} (1, 3)) \geq 2 k$ 成立。

4. 结论

本文利用反证法和数学归纳法证明玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数。根据好的画法的定义，给出了玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数为2k的一个好画法，从而得到玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数上界；由于玫瑰花窗图 $R_{3 k} (1, 3)$ 是广义周期图的一种，因此利用广义周期图的性质对图 $R_{3 k} (1, 3)$ 的边集进行分类，结合计数公式，利用所得的限制条件，探究每组边上的交叉计数，最终证得玫瑰花窗图 $R_{3 k} (1, 3)$ 的交叉数下界。由此得到 $c r (R_{3 k} (1, 3)) = 2 k$ ， $k \geq 3$ 。

参考文献

[1]	Turan, P. (1997) A Note of Welcome. Journal of Graph Theory, 1, 7-9. https://doi.org/10.1002/jgt.3190010105
[2]	Garey, M.R. and Johnson, D.S. (1993) Crossing Number Is NP-Complete. SIAM Journal on Algebraic & Discrete Methods, 1, 312-316. https://doi.org/10.1137/0604033
[3]	Exoo, Geoffrey, Harary, et al. (1981) The Crossing Numbers of Some Gen-eralized Petersen Graphs. Mathematica Scandinavica, 48, 184-188. https://doi.org/10.7146/math.scand.a-11910
[4]	Fiorini, S. (1986) On the Crossing Number of Generalized Pe-tersen Graph. Discrete Mathematic, 30, 221-242.
[5]	Richter, R.B. and Salazar, G. (2002) The Crossing Number of P(N, 3). Graphs and Combinatorics, 18, 381-394. https://doi.org/10.1007/s003730200028
[6]	林晓惠. 图论中若干难题的研究[D]: [硕士学位论文]. 大连: 大连理工大学, 2004.
[7]	马登举, 任韩, 卢俊杰. 广义Petersen图的交叉数[J]. 华东师范大学学报(自然科学版), 2005(1): 34-39.
[8]	Lin, X.H., Yang, Y.S., Zheng, W.P., et al. (2009) The Crossing Number of Gen-eralized Petersen Graphs with Small Order. Discrete Applied Mathematicas, 157, 1016-1023. https://doi.org/10.1016/j.dam.2008.01.012
[9]	Fiorini, S. and Gauci, J.B. (2003) The Crossing Number of the Generalized Petersen Graph P[3k, K]. Mathematica Bohemica, 128, 337-347. https://doi.org/10.21136/MB.2003.134001
[10]	郑百功. 冒泡排序图和广义Petersen图P(10, 3)的交叉数[D]: [硕士学位论文]. 大连: 大连理工大学, 2013.
[11]	Gauci, J.B. and Xuereb, C.Z. (2019) A Note on Isomorphic Gen-eralized Petersen Graphs with an Application to the Crossing Number of and . Discrete Mathematics Letters, 2, 44-46.
[12]	历莹. 一类无限图的交叉数[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2020.
[13]	卢妮. 广义Petersen图的交叉数[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2023.
[14]	白贺. 双广义Petersen图的交叉数[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2023.

为你推荐

友情链接