玫瑰花窗图R(3k, 3, 2)的交叉数

doi:10.12677/PM.2023.1310304

期刊菜单

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

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

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

Abstract: In 1738, the Swedish mathematician Euler solved the problem of seven bridges in Königsberg, and graph theory was born. 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 the proof, the research progress in the field of crossing number of graphs at home and abroad has been slow. In this paper, we mainly study the crossing number of rose window graph R(3k, 3, 2). Firstly, we get the upper bound of the crossover number of R(3k, 3, 2) based on the well-drawn method, and then we use the inverse method and the mathematical induction method to divide the set of edges of R(3k, 3, 2) into the 3k groups whose edges do not intersect, and discuss all the possible cases, so that we can prove that the lower bound of the crossover number of R(3k, 3, 2) is at least 3k, and thus we can prove that cr(R(3k, 3, 2)) = 3k, k ≥ 4.

文章引用：张瑜洁. 玫瑰花窗图R(3k, 3, 2)的交叉数[J]. 理论数学, 2023, 13(10): 2961-2967. https://doi.org/10.12677/PM.2023.1310304

1. 引言

众所周知，图论起源于一个非常经典的问题——哥尼斯堡七桥问题。1738年，瑞典数学家欧拉解决了哥尼斯堡七桥问题，图论由此诞生。图的交叉数是图论中一个重要的部分，近百年来，国内外很多学者都对图的交叉数这一问题进行研究。图的交叉数问题的研究，起源于20世纪40年代砖厂遇到的难题。第二次世界大战时期，Turan [1] 发现运砖车沿铁轨向仓库运砖时，车很容易在铁轨交点的位置脱节。他因此想到通过减少铁轨交叉个数来降低损失的方法，交叉数的概念由此而来。研究图的交叉数是一项富有意义但充满挑战性的工作，多年来，国内外众多学者潜心于图的交叉数课题的研究，但到目前为止，仍有众多图类的交叉数尚未解决，并且尚未找到能用来确定任意图的交叉数的有效算法。其实，在1983年，Garey和Johnson [2] 已经证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。下面主要介绍几类图的研究成果。

1.1. 完全图K_n

1960年，R. K. Guy [3] 对n个顶点的完全图 $K_{n}$ 的交叉数提出以下猜想：

$c r (K_{n}) = Z (n) = \frac{1}{4} \frac{n}{2} \frac{n - 1}{2} \frac{n - 2}{2} \frac{n - 3}{2}$ .

其中 $⌊ x ⌋$ 表示不超过任意实数x的最大整数。1969年，R. K. Guy [4] 对完全图的交叉数进一步研究，验证了当 $n \leq 10$ 时，上式成立。1970年，Kieitman [5] 给出了当n足够大时，完全图 $K_{n}$ 交叉数的下界：

$c r (K_{n}) \geq n (n - 1) (n - 2) (n - 3) / 80$ .

Richter等人 [6] [7] 证明了和 $K_{n}$ 和 $K_{n - 1}$ 之间的关系： $c r (K_{n}) \geq ⌈ \frac{n}{n - 4} \cdot c r (K_{n - 1}) ⌉$ 。

1.2. 完全二部图K_m_,n

1960年，Zarankiewicz [8] 给出了完全二部图 $K_{m, n}$ 交叉数的猜想：

$c r (K_{m, n}) = ⌊ \frac{m}{2} ⌋ ⌊ \frac{m - 1}{2} ⌋ ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋$ .

1970年，Kieitman [5] 证明了当 $\min (m, n) \leq 6$ 时，Zarankiewicz的猜想成立。1993年，Woodall [9] 验证了Zarankiewicz的猜想对于 $K_{7, 7}$ 和 $K_{7, 9}$ 成立。2003年，N. H. Nahas [10] 进一步研究当足够大时完全二部图的交叉数：

$c r (K_{m, n}) \geq \frac{1}{5} m (m - 1) ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ + 9.9 \times 10^{- 6} m^{2} n^{2}$ .

2007年，Klerk等人 [11] 给出了完全二部图 $K_{m, n}$ 的新下界：

$c r (K_{m, n}) \geq 0.8594 Z (m, n) .$

1.3. 广义Petersen图

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

${\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 [13] 给出广义Petersen图 $P (n, 3)$ 的交叉数的证明，但是，Richter和Salazar [14] 随后指出其证明存在错误，他们证明广义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年，林晓惠 [15] 得出了 $P (4 k + 2, 2 k)$ 等部分广义Petersen图的交叉数的上界；2005年，马登举等人证明了 $G (2 m + 1, m)$ 的交叉数 [16] ；2009年，杨元生等人利用算法给出了 $n \geq 16$ 时 $P (n, k)$ 的交叉数的精确值 [17] ；Fiorini和黄元秋等人分别用不同方法证明了 $P (3 k, k)$ 的交叉数 [18] ；2013年，郑百功证明了 $P (10, 3)$ 的交叉数 [19] 。2019年，Gauci和Xuereb [20] 证明了当 $k \geq 3$ 时有：

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

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

2020年，历莹 [21] 通过研究 $P (12, 5)$ 的子图的性质，证明得出 $P (12, 5)$ 的交叉数的下界至少是6，进而提出猜想：当 $k \geq 5$ 时， $c r (P (2 k + 2, k)) \geq k + 1$ 。

2. 玫瑰花窗图R(3k, 3, 2)的交叉数

2.1.玫瑰花窗图R(3k, 3, 2)的定义

在广义Petersen图 $P (3 k, 3)$ 的基础上添加一类边，得到玫瑰花窗图 $R (3 k, 3, 2)$ 。

设玫瑰花窗图 $R (3 k, 3, 2)$ 的顶点集为 $V (R (3 k, 3, 2)) = {a_{i}, b_{i} | 1 \leq i \leq 3 k}$ ，边集为 $E (R (3 k, 3, 2)) = {a_{i} a_{i + 1}, a_{i} b_{i}, b_{i} b_{i + 3}, b_{i} a_{i + 2}}, k \geq 4$ ，其中下标取模3k。取玫瑰花窗图 $R (3 k, 3, 2)$ 的子集 $H_{i}$ ，且有 $V (H_{i}) = {a_{i}, b_{i}, a_{i + 1}, b_{i + 3}, a_{i + 2}}$ ， $E (H_{i}) = {a_{i} a_{i + 1}, a_{i} b_{i}, b_{i} b_{i + 3}, b_{i} a_{i + 2}}$ ， $1 \leq i \leq 3 k$ ， $k \geq 4$ ，可得 $H_{i}$ 是 $R (3 k, 3, 2)$ 的一个可传递分解，其中 $E (R (3 k, 3, 2)) = \cup_{i = 1}^{3 k} H_{i}$ 。又有 $H_{i, j}$ 是 $H_{i}, H_{i + 1}, \dots, H_{j}$ 的并集，且 $f_{D} (H)$ 是H到所有非负实数集合的映射： $f_{D} (H) = c r_{D} (H) + c r_{D} (H, G \ E (H)) / 2$ 。画法D下的交叉数用 $c r (D)$ 或 $c r_{D} (G)$ 表示。

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

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

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

引理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$ 。

2.2. 玫瑰花窗图R(3k, 3, 2)的交叉数的上界

引理3 对于玫瑰花窗图 $R (3 k, 3, 2)$ ，当 $k \geq 4$ 时， $c r_{D} (R (3 k, 3, 2)) \leq 3 k$ 。

证明：图1给出了玫瑰花窗图 $R (3 k, 3, 2)$ 的一个有3k个交叉点的好的画法，因此，当 $k \geq 4$ 时， $c r_{D} (R (3 k, 3, 2)) \leq 3 k$ 。

Figure 1. A good drawing of with 3k crossings

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

2.3. 玫瑰花窗图R(3k, 3, 2)的交叉数的下界

令 $C_{i}$ 为圈 $a_{i} a_{i + 1} b_{i + 1} a_{i + 3} b_{i + 3} b_{i} a_{i}$ ，路径 $P_{0} = a_{1} a_{2} \dots a_{3 k}$ ， $P_{j} = b_{j} b_{j + 3} \dots b_{3 k - 3 + j}$ ，其中 $1 \leq j \leq 3$ ，对于路径P，如果 $a, b \in V (P)$ ，则 $a P v$ 表示P从a到b的连续顶点。

引理4 如果 $c r_{D} (C_{1}) = 1$ ，且 $c r_{D} (a_{1} a_{2}, b_{2} a_{4}) = 1$ ，则 $l_{1}^{D} \leq 4$ 。

证明：反证法。假设 $l_{1}^{D} \geq 5$ ，则 $f_{D} (H_{1, i}) < i$ ， $1 \leq i \leq 5$ 。若 $c r_{D} (a_{1} a_{2}, b_{2} a_{4}) = 1$ ，则 $D (C_{1})$ 同构于图2(a)。由 $f_{D} (H_{1}) < 1$ 可知，在画法D下 $H_{1}$ 中的其他边不能再被交叉，因此 $b_{1} a_{3}$ 干净，故 $a_{3} \in R_{2} \cup R_{0}$ 。

若 $a_{3}$ 在区域 $R_{2}$ 中， $b_{1} a_{3}$ 干净，由引理1及 $f_{D} (H_{1 ， 2}) < 2$ 知 $a_{2} a_{3}$ 只能与 $a_{4} b_{4}$ 相交， $D (C_{1} \cup a_{2} a_{3})$ 同构于图2(b)，再由引理1可知，路径 $a_{4} a_{5} b_{5} b_{2}$ 与圈 $a_{1} a_{2} a_{3} b_{1}$ 相交一次，与 $f_{D} (H_{1 ， 2}) < 2$ 相矛盾。

若 $a_{3}$ 在区域 $R_{0}$ 中， $b_{1} a_{3}$ 干净，由引理1知 $a_{2} a_{3}$ 与 $a_{4} b_{4}$ 相交至少相交两次，而D是一个好的画法，因此 $a_{2} a_{3}$ 干净， $D (C_{1} \cup a_{2} a_{3} \cup b_{1} a_{3})$ 同构于图2(c)，根据引理1可知，路径 $a_{4} a_{5} b_{3} b_{3 k} a_{3 k} a_{3 k - 1} b_{3 k - 1} b_{2}$ 和 $b_{4} b_{7} a_{7} b_{5} b_{2}$ 与 $a_{1} a_{2} a_{3} b_{1}$ 相交，与 $f_{D} (H_{1 ， 2}) < 2$ 相矛盾。

(a) (b) (c)

Figure 2. Subdrawings of D

图2. D的子画法

引理5 如果 $c r_{D} (C_{1}) = 1$ ，且 $c r_{D} (a_{1} a_{2}, a_{4} b_{4}) = 1$ ，则 $l_{1}^{D} \leq 6$ 。

证明：反证法。假设 $l_{1}^{D} \geq 7$ ，则 $f_{D} (H_{1, i}) < i$ ， $1 \leq i \leq 7$ 。若 $c r_{D} (a_{1} a_{2}, a_{4} b_{4}) = 1$ ，则 $D (C_{1})$ 同构于图3(a)。由 $f_{D} (H_{1}) < 1$ 可知，在画法D下 $H_{1}$ 中的其他边不能再被交叉，因此 $b_{1} a_{3}$ 干净，故 $a_{3} \in R_{1} \cup R_{0}$ 。

若 $a_{3}$ 在区域 $R_{1}$ 中， $b_{1} a_{3}$ 干净，由引理1及D是一个好的画法可知， $a_{3} a_{4}$ 不能与相邻边 $a_{4} b_{4}$ 相交， $a_{3} a_{4}$ 必定与圈 $b_{4} b_{1} a_{1} a_{2}$ 相交，与 $f_{D} (H_{1}) < 1$ 相矛盾。

若 $a_{3}$ 在区域 $R_{0}$ 中， $b_{1} a_{3}$ 干净，此时有 $f_{D} (H_{1, 4}) \geq 1$ ，考虑 $a_{2} a_{3}$ ，由 $f_{D} (H_{1, 4}) < 4$ 显然有以下四种情形： $a_{2} a_{3}$ 与 $a_{4} b_{2}$ 相交， $a_{2} a_{3}$ 与 $a_{4} b_{4}$ 相交， $a_{2} a_{3}$ 同时与 $a_{4} b_{2}$ 和 $a_{4} b_{4}$ 相交以及 $a_{2} a_{3}$ 干净，下面分别讨论这几种情形。

若 $a_{2} a_{3}$ 与 $a_{4} b_{2}$ 相交，则 $D (C_{1} \cup a_{2} a_{3} \cup b_{1} a_{3})$ 同构于图3(b)，此时有 $f_{D} (H_{1, 2}) \geq 1.5$ ，根据引理1可知，路径 $b_{4} a_{6} a_{5} a_{4}$ 与圈 $b_{1} a_{1} a_{2} a_{3}$ 相交，与 $f_{D} (H_{1, 2}) < 2$ 相矛盾。

若 $a_{2} a_{3}$ 与 $a_{4} b_{4}$ 相交，则 $D (C_{1} \cup a_{2} a_{3} \cup b_{1} a_{3})$ 同构于图3(c)，根据引理1可知，路径 $a_{1} a_{3 k} b_{3 k} a_{2}$ 与 $a_{1} b_{3 k - 1} b_{2}$ 和 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3}$ 相交，此时有 $f_{D} (H_{1 ， 4}) \geq 3$ ，考虑 $b_{2} b_{5}$ ，由 $f_{D} (H_{1, 4}) < 4$ 可知， $b_{2} b_{5}$ 与 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3}$ 不能相交，即 $b_{2} b_{5}$ 干净，因此有， $b_{5} \in R_{2} \cup R_{3}$ 。

若 $b_{5} \in R_{2}$ ， $b_{2} b_{5}$ 干净，根据引理1有路径 $b_{5} b_{8} a_{8} a_{9} b_{7} b_{4}$ 和 $b_{5} a_{5} a_{6} b_{4}$ 与 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3}$ 相交，与 $f_{D} (H_{1, 4}) < 4$ 相矛盾。

若 $b_{5} \in R_{3}$ ， $b_{2} b_{5}$ 干净，此时由 $f_{D} (H_{1, 4}) \geq 3$ 可知 $a_{3} a_{4}$ 是干净的， $D (C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4} \cup b_{2} b_{5})$ 同构于图3(d)。考虑 $C_{2} : a_{2} a_{3} b_{3} a_{5} b_{5} b_{2} a_{2}$ ，对于 $a_{3} b_{3} a_{5} b_{5}$ 而言， $D (C_{1, 2} \cup a_{3} a_{4})$ 同构于图3(e)、图3(f)、图3(g)和图3(h)。

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k)

Figure 3. Subdrawings of D

图3. D的子画法

情况1 在图3(e)情形下，根据 $f_{D} (H_{1, 5}) \geq 3$ 且由引理1知路径 $a_{1} a_{3 k} b_{3 k} a_{2}$ ， $a_{1} b_{3 k - 1} b_{2}$ ， $b_{3} b_{6} a_{6} b_{4}$ 和 $b_{3} b_{3 k} P_{3} b_{9} a_{9} b_{7} b_{4}$ 与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾。

情况2 在图3(f)情形下，根据 $f_{D} (H_{1, 5}) \geq 3$ 且由引理1知 $a_{4} a_{5}$ 有边必然与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，因此 $f_{D} (H_{1, 5}) \geq 4$ ，再由引理1知路径 $a_{1} a_{3 k} b_{3 k} a_{2}$ 和 $a_{1} b_{3 k - 1} b_{2}$ 与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾。

情况3 在图3(g)情形下，根据 $f_{D} (H_{1, 5}) \geq 3$ 且由引理1知路径 $a_{1} a_{3 k} b_{3 k} a_{2}$ ， $a_{1} b_{3 k - 1} b_{2}$ ， $b_{3} b_{6} a_{6} b_{4}$ 和 $b_{3} b_{3 k} P_{3} b_{9} a_{9} b_{7} b_{4}$ 与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾。

情况4 在图3(h)情形下，根据引理1可知路径 $a_{1} b_{3 k - 1} P_{2} b_{8} b_{5}$ 和 $a_{1} a_{3 k} b_{3 k - 2} P_{1} b_{7} a_{7} b_{5}$ 与 $H_{1, 4}$ 相交，此时 $f_{D} (H_{1 ， 4}) \geq 3$ ，因此在画法D下 $H_{1, 4}$ 中的其他边干净，继续考虑 $b_{3} b_{6}, a_{4} a_{5}, b_{4} a_{6}, b_{4} b_{7}$ 这几条边，如果相交的话是只能与 $a_{5} b_{5}$ 相交，由D是好的画法可知 $a_{4} a_{5}$ 不能与相邻边 $a_{5} b_{5}$ 相交；若 $b_{3} b_{6}$ 与 $a_{5} b_{5}$ 相交，则 $f_{D} (H_{1, 5}) \geq 4$ ，根据引理1可知路径 $b_{4} a_{6} b_{6}$ 和 $b_{4} b_{7} b_{10} a_{10} a_{9} b_{9} b_{6}$ 与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾；若 $b_{4} a_{6}$ 与 $a_{5} b_{5}$ 相交，则 $f_{D} (H_{1, 5}) \geq 4$ ，根据引理1可知路径 $b_{3} b_{6} a_{6}$ 和 $b_{3} b_{3 k} a_{3 k} a_{3 k - 1} a_{3 k - 2} P_{0} a_{7} a_{6}$ 与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾；若 $b_{4} b_{7}$ 与 $a_{5} b_{5}$ 相交，则 $f_{D} (H_{1, 5}) \geq 4$ ，根据引理1可知路径 $b_{3} b_{6} a_{8} a_{9} a_{10} b_{10} b {}_{7}$ 和 $b_{3} b_{3 k} P_{3} b_{9} a_{9} b_{7}$ 与 $C_{1, 2} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾，因此 $b_{3} b_{6}, b_{4} a_{6}, b_{4} b_{7}$ 都是干净的。继续考虑 $C_{3} : a_{3} a_{4} b_{4} a_{6} b_{6} b_{3} a_{3}$ ，根据引理1及D是一个好的画法可知，路径 $b_{4} a_{6} b_{6} b_{3}$ 及 $a_{5} a_{6}$ 干净， $D (C_{1, 3} \cup a_{5} a_{6})$ 同构于图3(i)。又由引理1可知，路径 $b_{6} P_{3} b_{3 k} a_{3 k} a_{1}$ 与 $b_{6} a_{8} b_{8} P_{2} b_{3 k - 1} a_{1}$ 和 $C_{1, 3} \cup a_{5} a_{6}$ 相交至少交两次，又有路径 $b_{1} b_{3 k - 2} a_{3 k - 2} a_{3 k - 1} b_{3 k - 1} b_{2}$ 与 $b_{3} b_{3 k} a_{2}$ 和 $C_{1, 3} \cup a_{5} a_{6}$ 相交，与 $f_{D} (H_{1, 5}) < 5$ 相矛盾。

若 $a_{2} a_{3}$ 同时与 $a_{4} b_{2}$ 和 $a_{4} b_{4}$ 相交，根据引理1，此时与 $f_{D} (H_{1, 2}) < 2$ 相矛盾。

若 $a_{2} a_{3}$ 干净，则 $D (C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3})$ 同构于图3(j)，此时根据引理1有路径 $b_{4} a_{6} a_{5} a_{4}$ 与 $b_{4} P_{1} b_{3 k - 2} b_{1} a_{3} a_{4}$ 和圈 $a_{1} a_{2} a_{3} b_{1}$ 相交，此时 $f_{D} (H_{1, 2}) \geq 1.5$ ，因此在画法D下 $H_{1, 2}$ 的其他边干净，故 $a_{3} a_{4}$ 也是干净的， $D (C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4})$ 同构于图3(k)。根据引理1可知，路径 $b_{2} b_{5} a_{7} b_{7} P_{1} b_{3 k - 2} b_{1}$ ， $b_{2} b_{3 k - 1} a_{1}$ ， $a_{1} a_{3 k} b_{3 k} a_{2}$ 和 $b_{4} a_{6} a_{5} a_{4}$ 与 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4}$ 相交，因此 $f_{D} (H_{1, 4}) \geq 3$ ，考虑路径 $b_{2} b_{5} a_{7} b_{7} P_{1} b_{3 k - 2} b_{1}$ 中的边 $b_{2} b_{5}$ ，若边 $b_{2} b_{5}$ 与 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4}$ 相交，则 $f_{D} (H_{1, 4}) \geq 3.5$ ，即在画法D下 $H_{1, 4}$ 的其他边干净；若边 $b_{2} b_{5}$ 不与 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4}$ 相交，则 $b_{5} \in R_{2} \cup R_{3}$ ，由引理1知 $b_{5}$ 不论在区域 $R_{2}$ 或区域 $R_{3}$ ，都有路径 $a_{7} b_{7} P_{1} b_{3 k - 2} b_{1}$ 与 $b_{8} a_{10} a_{9} b_{7} b_{4}$ 和 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4}$ 相交，则 $f_{D} (H_{1, 4}) \geq 3.5$ ，因此在画法D下 $H_{1, 4}$ 的其他边干净；同理考虑路径 $b_{4} a_{6} a_{5} a_{4}$ 中的边 $b_{4} a_{6}$ 和 $a_{4} a_{5}$ ，由 $f_{D} (H_{1, 4}) \geq 3.5$ 可知边 $b_{4} a_{6}$ 和 $a_{4} a_{5}$ 干净，则 $a_{6} \in R_{1} \cup R_{4}$ ， $a_{5} \in R_{0} \cup R_{2} \cup R_{3}$ ，显然 $a_{5}, a_{6}$ 不在同一区域，根据引理1， $a_{5} a_{6}$ 与 $C_{1} \cup b_{1} a_{3} \cup a_{2} a_{3} \cup a_{3} a_{4}$ 相交，与 $f_{D} (H_{1, 4}) < 4$ 相矛盾。证毕。

3. 结论

本文利用反证法和数学归纳法证明玫瑰花窗图R(3k, 3, 2)的交叉数。根据好的画法，得到了交叉数为3k的一个好的画法，从而得到玫瑰花窗图R(3k, 3, 2)的交叉数上界，进而利用玫瑰花窗图R(3k, 3, 2)特有的结构，结合不同的计数公式，对其边集进行分类，利用所得的限制条件，探究每组边上的交叉计数，最终证得图R(3k, 3, 2)的交叉数下界，由此得到玫瑰花窗图R(3k, 3, 2)的交叉数为3k。

参考文献

[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, 4, 312-316. https://doi.org/10.1137/0604033
[3]	Guy, R.K. (1960) A Combinatorial Problem. Malaysian Mathematical So-ciety, 7, 68-72.
[4]	Guy, R.K. (1969) Proof Techniques in Graph Theory. Academic Press, New York.
[5]	Kleitman, D.J. (1970) The Crossing Number of K5,n. Journal of Combinatorial Theory, 9, 315-325. https://doi.org/10.1016/S0021-9800(70)80087-4
[6]	Pan, S. and Richter, R.B. (2007) The Crossing Number of K11 Is 100. Journal of Graph Theory, 56, 128-134. https://doi.org/10.1002/jgt.20249
[7]	Dan, M.Q., Pan, S. and Richter, R.B. (2015) On the Crossing Number of K1,3. Journal of Combinatorial Theory Series B, 115, 224-235.
[8]	Zarankiewicz, K. (1954) On a Problem of P. Turan Concerning Graphs. Fundanmenta Mathematicae, 41, 137-145. https://doi.org/10.4064/fm-41-1-137-145
[9]	Woodall, D.R. (1993) Cyclic-Order Graphs and Zarankiewicz’s Crossing Number Conjecture. Journal of Graph Theory, 17, 657-671. https://doi.org/10.1002/jgt.3190170602
[10]	Nahas, N. (2003) On the Crossing Number of Km,n. The Electronic Journal of Combinatorics, 10, 1-6. https://doi.org/10.37236/1748
[11]	Klerk, E.D., Pasechnik, D.V. and Schrijver, A. (2007) Reduction of Symmetric Semidifinite Programs Using the Regular*-Representation. Mathematical Programming, 109, 613-624. https://doi.org/10.1007/s10107-006-0039-7
[12]	Exoo, G., Harary, F. and Kabell, J. (1981) The Crossings of Some Generalized Petersen Graphs. Mathematic Scandinavica, 48, 184-188. https://doi.org/10.7146/math.scand.a-11910
[13]	Fiorini, S. (1986) On the Crossing Number of Generalized Pe-tersen Graph. Discrete Mathematic, 30, 221-242.
[14]	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
[15]	林晓惠. 图论中若干难题的研究[D]: [硕士学位论文]. 大连: 大连理工大学, 2004.
[16]	马登举, 任韩, 卢俊杰. 广义Petersen图G(2m+1,m)的交叉数[J]. 华东师范大学学报(自然科学版), 2005(1): 34-39.
[17]	Lin, X.H., Yang, Y.S., Zheng, W.P., Shi, L. and Lu, W.M. (2009) The Crossing Number of Generalized Petersen Graphs with Small Order. Discrete Applied Mathematicas, 157, 1016-1023. https://doi.org/10.1016/j.dam.2008.01.012
[18]	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
[19]	郑百功. 冒泡排序图Bn和广义Petersen图P(10,3)的交叉数[D]: [硕士学位论文]. 大连: 大连理工大学, 2013.
[20]	Gauci, J.B. and Xuereb, C.Z. (2019) A Note on Isomorphic Gen-eralized Petersen Graphs with an Application to the Crossing Number of GP(3k-1,k) and GP(3k+1,k). Discrete Mathematics Letters, 2, 44-46.
[21]	历莹. 一类无限图的交叉数[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2020.

为你推荐

友情链接