一类可传递分解图的交叉数

doi:10.12677/AAM.2023.122060

期刊菜单

一类可传递分解图的交叉数
The Crossing Number of a Class of Transitive Decomposition Graphs

DOI: 10.12677/AAM.2023.122060, PDF, HTML, XML, 下载: 312 浏览: 427
作者: 乔凤秋：辽宁师范大学数学学院，辽宁大连
关键词: 交叉数；六边形图；可传递分解；Crossing Number； Hexagonal Graph； Transitive Decomposition

摘要: 图的交叉数是拓扑图论中重要的一个分支，国内外诸多学者对图的交叉数这一问题进行广泛的关注和深入的研究，Garey和Johnson证明了计算图的交叉数是NP-完全问题。本文令cr(G)表示图G的交叉数，主要利用弱积图C_n × K₃的一个传递分解{H₁,H₂,...H_n}对其交叉数进行研究。首先构造了六边形图C2k × K3交叉数较少的画法，给出交叉数的上界，然后采用数学归纳法和反证法，将C_2k × K₃的边集分成边不相交的2k组，讨论所有可能情况，从而证得cr(C_2k × K₃) = 4k，k ≥ 3。

Abstract: The crossing number of graphs is an important branch of topological graph theory. Many scholars at home and abroad have made extensive attention and in-depth research on the crossing number of graphs. Garey and Johnson proved that the calculation of the crossing number of graphs is a NP-complete problem. In this paper, let cr(G) denote the crossing number of a graph G, we study the crossing number of C_n × K₃ by using a transitive decomposition {H₁,H₂,...H_n} . First, we construct a method of drawing the hexagon graph C_2k × K₃ with less crossing number, and give the upper bound of the crossing number. Then, the edge set of C2k × K3 is divided into 2k groups with disjoint edges by mathematical induction and reduction to absurdity. All possible cases are discussed, and cr(C_2k × K₃) = 4k, k ≥ 3 is proved.

文章引用：乔凤秋. 一类可传递分解图的交叉数[J]. 应用数学进展, 2023, 12(2): 574-581. https://doi.org/10.12677/AAM.2023.122060

1. 引言

图论是组合数学的一个重要分支，已有数百年之久的研究历史。拓扑图论作为图论的一个分支 [1] ，其计算结果在社会科学、计算科学和自然科学等多个领域具有广泛的应用 [2] 。图的交叉数是图论中一个重要的部分，国内外很多学者都对这一问题进行研究 [3] ，但由于探究和证明难度比较大，至今为止，图的交叉数的研究成果大部分集中在典型的图类上 [4] ，只得到了较少图族的交叉数的精确值 [5] 。

设A，B，C为图G的边集的互不相交的子集，则对于图G的任意画法D，有

$c r_{D} (A \cup B) = c r_{D} (A) + c r_{D} (B) + c r_{D} (A, B)$ ,

$c r_{D} (A \cup B, C) = c r_{D} (A, C) + c r_{D} (B, C)$ .

引理1 如果在画法D中存在一条被交叉的边e，并且删除边e后得到了新的画法D^* [6] ，那么 $c r (D) \geq c r (D^{*}) + 1$ 。

引理2 画法D下的交叉数用cr(D)或cr_D(G)表示 [7] 。设H是G的子图且f_D(H)是H到所有非负实数集合的映射： $f_{D} (H) = c r_{D} (H) + c r_{D} (H, G \ E (H)) / 2$ 。

引理3 令c是一个正实数。假设 $G_{1}, G_{2}, \dots, G_{t}$ 是图G的传递分解 [8] ，若对图G的每个好的画法D，有 $\max {l_{c}^{D} (G_{1}), l_{c}^{D} (G_{2}), \dots, l_{c}^{D} (G_{t})} \leq t$ ，则 $c r (G) \geq ⌈ c t ⌉$ 。

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

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

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

2. 弱积图C_2k × K₃的交叉数

2.1. 弱积图C_n × K₃的定义

设弱积图的顶点集 $V (C_{n} \times K_{3}) = {v_{j}^{i} : 1 \leq i \leq n, 1 \leq j \leq 3}$ ，边集 $E (C_{n} \times K_{3}) = {v_{j}^{i} v_{j + 1}^{i + 1} : 1 \leq i \leq n, 1 \leq j \leq 3} \cup {v_{j}^{i} v_{j + 2}^{i + 1} : 1 \leq i \leq n, 1 \leq j \leq 3}$ ，其中上标和下标分别取模n和3。令H_i是由 ${v_{j}^{i} : 1 \leq j \leq 3} \cup {v_{j}^{i + 1} : 1 \leq j \leq 3}$ 诱导的 $C_{n} \times K_{3}$ 的子图，其中 $1 \leq i \leq n$ 。很容易得到 ${H_{1}, H_{2}, \dots, H_{n}}$ 是 $C_{n} \times K_{3}$ 的一个可传递分解。图1给出了H_i满足条件的3个好的画法，它们依次具有交叉数1、1、0。

Figure 1. Good drawings of H₁

图1. H₁的好的画法

2.2. 弱积图C_2k × K₃的交叉数的上界

引理5 对于弱积图 $C_{2 k} \times K_{3}$ ，当 $k \geq 3$ 且 $f_{D} (H_{i}) < 2$ 时， $c r_{D} (C_{2 k} \times K_{3}) \leq 4 k$ 。

证明：图2给出了 $C_{2 k} \times K_{3}$ 的一个有4k个交叉点的好的画法，因此，当 $k \geq 3$ 且 $f_{D} (H_{i}) < 2$ 时， $c r_{D} (C_{2 k} \times K_{3}) \leq 4 k$ 。

Figure 2. A good drawing of with 4k crossings

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

2.3. 弱积图C_2k × K₃的交叉数的下界

引理6 令D是 C_2k × K₃的交叉数的下界的一个好的画法，其中 $k \geq 3$ 。若 $l_{2}^{D} (H_{i}) > 1$ 且 $D (H_{i})$ 与图1(a)同构，则 $l_{2}^{D} (H_{i}) = 2$ ， $1 \leq i \leq 2 k$ 。

证明：反证法。不失一般性，假设当 $D (H_{1})$ 同构于图1(a)时，有 $l_{2}^{D} (H_{1}) > 2$ 。通过 $l_{2}^{D} (H_{1}) > 2$ ，得到 $f_{D} (H_{1}) < 2$ 和 $f_{D} (H_{1, 2}) < 4$ 。若顶点 $v_{1}^{3}$ 在区域R₁内，则由引理2可知，路径 $v_{1}^{3} v_{2}^{4} v_{3}^{3} v_{1}^{2}$ 和 $v_{1}^{3} v_{3}^{4} v_{2}^{3} v_{1}^{2}$ 各交路径 $v_{2}^{1} v_{3}^{2} v_{1}^{1} v_{2}^{2} v_{3}^{1}$ 一次，与 $f_{D} (H_{1}) < 2$ 矛盾，因此顶点 $v_{1}^{3}$ 不在区域R₁内。类似地，顶点 $v_{1}^{3}$ 不在区域R₂内，则顶点 $v_{1}^{3}$ 在区域R₀内。由于 $v_{2}^{3}$ 和 $v_{3}^{3}$ 与 $v_{1}^{3}$ 在同构意义下等价，与上述证明过程类似，可得到 $v_{2}^{3}$ 和 $v_{3}^{3}$ 也位于区域R₀内。通过 $f_{D} (H_{1}) < 2$ 且 $c r_{D} (H_{1}) = 1$ ，得到 $c r_{D} (H_{1}, H_{2}) \leq 1$ 。因此，我们分别考虑以下两种情况。

情况1 $c r_{D} (H_{1}, H_{2}) = 1$ 。

假设 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ ，通过 $f_{D} (H_{1, 2}) < 4$ ，得到 $c r_{D} (H_{2}) \leq 1$ 。若 $c r_{D} (H_{2}) = 1$ ，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图3(a)。根据引理2可知，路径 $v_{1}^{1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{1}^{1} v_{3}^{2 k} v_{2}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交圈 $v_{3}^{2} v_{2}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。若 $f_{D} (H_{1, 2}) < 4$ ，则 $D (H_{1} \cup v_{2}^{2} v_{3}^{3} v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图3(b)。根据引理2可知，路径 $v_{2}^{3} v_{3}^{4} v_{1}^{5} v_{3}^{6} v_{1}^{7} v_{3}^{8} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{2}^{1}$ 和 $v_{2}^{3} v_{1}^{4} v_{3}^{5} v_{1}^{6} v_{3}^{7} v_{1}^{8} \dots v_{3}^{2 k - 1} v_{1}^{2 k} v_{2}^{1}$ 各交圈 $v_{1}^{2} v_{3}^{1} v_{2}^{2} v_{3}^{3} v_{1}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。

假设 $c r_{D} (H_{1}, v_{1}^{2} v_{2}^{3} v_{3}^{2}) = 1$ 或 $c r_{D} (H_{1}, v_{1}^{2} v_{3}^{3} v_{2}^{2}) = 1$ ，不失一般性，假定 $c r_{D} (H_{1}, v_{1}^{2} v_{3}^{3} v_{2}^{2}) = 1$ 。若 $c r_{D} (H_{2}) = 1$ ，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图3(a)，与 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ 情况相同，得到矛盾。因此 $c r_{D} (H_{2}) = 0$ ，即顶点 $v_{1}^{3}$ 和 $v_{2}^{3}$ 产生的边都是干净的，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2} v_{1}^{3} v_{2}^{2})$ 同构于图3(c)。根据引理2可知，路径 $v_{1}^{3} v_{2}^{4} v_{1}^{5} v_{2}^{6} \dots v_{1}^{2 k - 1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{1}^{3} v_{3}^{4} v_{2}^{5} v_{1}^{6} v_{2}^{7} v_{1}^{8} \dots v_{2}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交圈 $v_{3}^{2} v_{2}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次；路径 $v_{2}^{1} v_{3}^{2 k} v_{1}^{1}$ 和 $v_{2}^{3} v_{1}^{4} v_{3}^{5} v_{2}^{6} v_{3}^{7} v_{2}^{8} \dots v_{3}^{2 k - 1} v_{2}^{2 k} v_{1}^{1}$ 各交路径 $v_{2}^{1} v_{3}^{2} v_{1}^{3} v_{2}^{2} v_{3}^{1}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。

情况2 $c r_{D} (H_{1}, H_{2}) = 0$ 。通过 $f_{D} (H_{1, 2}) < 4$ ，得到 $c r_{D} (H_{2}) \leq 2$ 。

若 $c r_{D} (H_{2}) = 2$ ，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图3(a)，与 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ 情况相同，得到矛盾。

若 $c r_{D} (H_{2}) = 1$ ，不失一般性，假设路径 $v_{1}^{2} v_{3}^{3} v_{2}^{2}$ 被交，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2} v_{1}^{3} v_{2}^{2})$ 同构于图3(c)，与 $c r_{D} (H_{1}, v_{1}^{2} v_{3}^{3} v_{2}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 0$ 情况相同，得到矛盾。

若 $c r_{D} (H_{2}) = 0$ ，则 $D (H_{1, 2})$ 的画法唯一确定，同构于图3(d)。由引理2可知，路径 $v_{1}^{3} v_{2}^{4} v_{1}^{5} v_{2}^{6} \dots v_{1}^{2 k - 1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{3}^{3} v_{1}^{4} v_{3}^{5} v_{1}^{6} \dots v_{3}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交圈 $v_{3}^{2} v_{2}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次；路径 $v_{2}^{3} v_{3}^{4} v_{2}^{5} v_{3}^{6} \dots v_{2}^{2 k - 1} v_{3}^{2 k} v_{1}^{1}$ 和 $v_{3}^{3} v_{2}^{4} v_{3}^{5} v_{2}^{6} \dots v_{3}^{2 k - 1} v_{2}^{2 k} v_{1}^{1}$ 各交路径 $v_{2}^{1} v_{3}^{2} v_{1}^{3} v_{2}^{2} v_{3}^{1}$ 一次；路径 $v_{1}^{3} v_{3}^{4} v_{1}^{5} v_{3}^{6} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{2}^{1}$ 和 $v_{2}^{3} v_{1}^{4} v_{2}^{5} v_{1}^{6} \dots v_{2}^{2 k - 1} v_{1}^{2 k} v_{2}^{1}$ 各交圈 $v_{1}^{2} v_{3}^{1} v_{2}^{2} v_{3}^{3} v_{1}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。证毕。

Figure 3. Subdrawings of H_1,2

图3. H_1,2的子画法

引理7 令D是 $C_{2 k} \times K_{3}$ 的一个好的画法，其中 $k \geq 3$ 。若 $l_{2}^{D} (H_{i}) > 1$ 且 $D (H_{i})$ 与图1(b)同构，则 $l_{2}^{D} (H_{i}) = 2$ ， $1 \leq i \leq 2 k$ 。

证明：反证法。不失一般性，假设当 $D (H_{1})$ 同构于图1(b)时，有 $l_{2}^{D} (H_{1}) > 2$ 。通过 $l_{2}^{D} (H_{1}) > 2$ ，得到 $f_{D} (H_{1}) < 2$ 和 $f_{D} (H_{1, 2}) < 4$ 。若顶点 $v_{1}^{3}$ 在区域R₁内，则由引理2可知，路径 $v_{1}^{3} v_{2}^{2}$ 和 $v_{1}^{3} v_{3}^{4} v_{2}^{3} v_{1}^{2}$ 各交路径 $v_{2}^{2} v_{1}^{1} v_{3}^{2} v_{2}^{1}$ 一次，与 $f_{D} (H_{1}) < 2$ 矛盾，因此顶点 $v_{1}^{3}$ 不在区域R₁内。若顶点 $v_{1}^{3}$ 在区域R₂内，则由引理2可知，路径 $v_{1}^{3} v_{3}^{2}$ 和 $v_{1}^{3} v_{3}^{4} v_{2}^{3} v_{3}^{2}$ 各交路径 $v_{1}^{1} v_{2}^{2} v_{3}^{1} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次，与 $f_{D} (H_{1}) < 2$ 矛盾，因此顶点 $v_{1}^{3}$ 不在区域R₂内，则顶点 $v_{1}^{3}$ 在区域R₀内。由于 $v_{2}^{3}$ 和 $v_{3}^{3}$ 与 $v_{1}^{3}$ 在同构意义下等价，与上述证明的过程类似，可以得到顶点 $v_{2}^{3}$ 和 $v_{3}^{3}$ 也位于区域R₀内。通过 $f_{D} (H_{1}) < 2$ 且 $c r_{D} (H_{1}) = 1$ ，得到 $c r_{D} (H_{1}, H_{2}) \leq 1$ 。因此，我们分别考虑以下两种情况。

Figure 4. Subdrawings of H_1,2

图4. H_1,2的子画法

情况1 $c r_{D} (H_{1}, H_{2}) = 1$ 。

假设 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ ，通过 $f_{D} (H_{1, 2}) < 4$ ，得到 $c r_{D} (H_{2}) \leq 1$ 。若 $c r_{D} (H_{2}) = 1$ ，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图4(a)。根据引理2可知，路径 $v_{1}^{1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{1}^{1} v_{3}^{2 k} v_{2}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交圈 $v_{3}^{2} v_{2}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。若 $c r_{D} (H_{2}) = 0$ ，则 $D (H_{1} \cup v_{2}^{2} v_{3}^{3} v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图4(b)。根据引理2可知，路径 $v_{3}^{3} v_{2}^{4} v_{1}^{5} v_{3}^{6} v_{1}^{7} v_{3}^{8} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{2}^{1}$ 和 $v_{3}^{3} v_{1}^{4} v_{3}^{5} v_{1}^{6} \dots v_{3}^{2 k - 1} v_{1}^{2 k} v_{2}^{1}$ 各交圈 $v_{1}^{2} v_{3}^{1} v_{2}^{2} v_{1}^{1} v_{3}^{2} v_{2}^{3} v_{1}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。

假设 $c r_{D} (H_{1}, v_{1}^{2} v_{3}^{3} v_{2}^{2}) = 1$ ，若 $c r_{D} (H_{2}) = 1$ ，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图4(a)，与 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ 情况相同，得到矛盾。因此 $c r_{D} (H_{2}) = 0$ ，即顶点 $v_{1}^{3}$ 和 $v_{2}^{3}$ 产生的边都是干净的，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2} v_{1}^{3} v_{2}^{2})$ 同构于图4(c)。根据引理2可知，路径 $v_{1}^{1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{1}^{1} v_{3}^{2 k} v_{2}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交圈 $v_{3}^{2} v_{2}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次；路径 $v_{1}^{3} v_{2}^{4} v_{3}^{5} v_{1}^{6} v_{3}^{7} v_{1}^{8} \dots v_{3}^{2 k - 1} v_{1}^{2 k} v_{2}^{1}$ 和 $v_{1}^{3} v_{3}^{4} v_{1}^{5} v_{3}^{6} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{2}^{1}$ 各交圈 $v_{1}^{2} v_{3}^{1} v_{2}^{2} v_{1}^{1} v_{3}^{2} v_{2}^{3} v_{1}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。

假设 $c r_{D} (H_{1}, v_{1}^{2} v_{2}^{3} v_{3}^{2}) = 1$ ，若 $c r_{D} (H_{2}) = 1$ ，则 $D (H_{1} \cup v_{1}^{2} v_{3}^{3} v_{2}^{2})$ 同构于图4(d)。根据引理2可知，路径 $v_{1}^{1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{1}^{1} v_{3}^{2 k} v_{2}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交路径 $v_{1}^{1} v_{2}^{2} v_{3}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。因此 $c r_{D} (H_{2}) = 0$ ，即顶点 $v_{1}^{3}$ 和 $v_{3}^{3}$ 产生的边都是干净的，则 $D (H_{1} \cup v_{1}^{2} v_{3}^{3} v_{2}^{2} v_{1}^{3} v_{3}^{2})$ 同构于图4(e)。经过检验，很容易得到 $D (H_{1, 2})$ 与图5中的其中一个图同构。

若 $D (H_{1, 2})$ 同构于图5(a)，则根据引理2可知，路径 $v_{1}^{3} v_{3}^{4} v_{1}^{5} v_{3}^{6} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{2}^{1}$ 和 $v_{3}^{3} v_{1}^{4} v_{3}^{5} v_{1}^{6} \dots v_{3}^{2 k - 1} v_{1}^{2 k} v_{2}^{1}$ 各交路径 $v_{1}^{1} v_{2}^{2} v_{3}^{1} v_{1}^{2} v_{2}^{3} v_{3}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。若 $D (H_{1, 2})$ 同构于图5(b)，则根据引理2可知，路径 $v_{2}^{1} v_{1}^{2 k} v_{3}^{1}$ 和 $v_{1}^{3} v_{2}^{4} v_{1}^{5} v_{2}^{6} \dots v_{1}^{2 k - 1} v_{2}^{2 k} v_{3}^{1}$ 各交圈 $v_{1}^{2} v_{3}^{3} v_{2}^{2} v_{1}^{1} v_{3}^{2} v_{2}^{3} v_{1}^{2}$ 一次；路径 $v_{1}^{3} v_{3}^{4} v_{1}^{5} v_{3}^{6} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{1}^{1}$ 和 $v_{3}^{3} v_{2}^{4} v_{3}^{5} v_{2}^{6} \dots v_{3}^{2 k - 1} v_{2}^{2 k} v_{1}^{1}$ 各交路径 $v_{2}^{1} v_{3}^{2} v_{2}^{3} v_{1}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。

Figure 5. Subdrawings of H_1,2

图5. H_1,2的子画法

情况2 $c r_{D} (H_{1}, H_{2}) = 0$ 。通过 $f_{D} (H_{1, 2}) < 4$ ，得到 $c r_{D} (H_{2}) \leq 2$ 。

若 $c r_{D} (H_{2}) = 2$ ，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图4(a)，与 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ 情况相同，得到矛盾。

若 $c r_{D} (H_{2}) = 1$ ，假设 $v_{2}^{2} v_{1}^{3} v_{3}^{2}$ 路径被交，则 $D (H_{1} \cup v_{2}^{2} v_{3}^{3} v_{1}^{2} v_{2}^{3} v_{3}^{2})$ 同构于图4(b)；假设 $v_{1}^{2} v_{3}^{3} v_{2}^{2}$ 路径被交，则 $D (H_{1} \cup v_{1}^{2} v_{2}^{3} v_{3}^{2} v_{1}^{3} v_{2}^{2})$ 同构于图4(c)；假设 $v_{1}^{2} v_{2}^{3} v_{3}^{2}$ 路径被交，则 $D (H_{1} \cup v_{1}^{2} v_{3}^{3} v_{2}^{2} v_{1}^{3} v_{3}^{2})$ 同构于图4(e)。分别与 $c r_{D} (H_{1}, v_{2}^{2} v_{1}^{3} v_{3}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ ， $c r_{D} (H_{1}, v_{1}^{2} v_{3}^{3} v_{2}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ 和 $c r_{D} (H_{1}, v_{1}^{2} v_{2}^{3} v_{3}^{2}) = 1$ 且 $c r_{D} (H_{2}) = 1$ 情况相同，得到矛盾。

若 $c r_{D} (H_{2}) = 0$ ，则 $D (H_{1, 2})$ 的画法唯一确定，同构于图4(f)。由引理2可知，路径 $v_{1}^{3} v_{2}^{4} v_{1}^{5} v_{2}^{6} \dots v_{1}^{2 k - 1} v_{2}^{2 k} v_{1}^{1}$ 和 $v_{1}^{3} v_{3}^{4} v_{1}^{5} v_{3}^{6} \dots v_{1}^{2 k - 1} v_{3}^{2 k} v_{1}^{1}$ 各交圈 $v_{3}^{2} v_{2}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次；路径 $v_{2}^{3} v_{1}^{4} v_{3}^{5} v_{2}^{6} v_{3}^{7} v_{2}^{8} \dots v_{3}^{2 k - 1} v_{2}^{2 k} v_{3}^{1}$ 和 $v_{2}^{3} v_{3}^{4} v_{2}^{5} v_{1}^{6} v_{2}^{7} v_{1}^{8} \dots v_{2}^{2 k - 1} v_{1}^{2 k} v_{3}^{1}$ 各交路径 $v_{1}^{1} v_{2}^{2} v_{3}^{3} v_{1}^{2} v_{2}^{1} v_{3}^{2}$ 一次；路径 $v_{3}^{3} v_{1}^{4} v_{2}^{5} v_{3}^{6} v_{2}^{7} v_{3}^{8} \dots v_{2}^{2 k - 1} v_{3}^{2 k} v_{2}^{1}$ 和 $v_{3}^{3} v_{2}^{4} v_{3}^{5} v_{1}^{6} v_{3}^{7} v_{1}^{8} \dots v_{3}^{2 k - 1} v_{1}^{2 k} v_{2}^{1}$ 各交圈 $v_{1}^{2} v_{3}^{1} v_{2}^{2} v_{1}^{1} v_{3}^{2} v_{2}^{3} v_{1}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。证毕。

引理8令D是 $C_{2 k} \times K_{3}$ 的一个好的画法且 $l_{2}^{D} (H_{i}) > 1$ ，其中 $k \geq 3$ 。若 $c r_{D} (H_{i}, H_{i + 1}) = 3$ 且 $D (H_{i, i + 1})$ 与图6中的其中一个图同构，则 $v_{1}^{i + 3}, v_{2}^{i + 3}$ 和 $v_{3}^{i + 3}$ 均在区域R₀内，其中 $1 \leq i \leq 2 k$ 。

Figure 6. Subdrawings of H_1,2

图6. H_1,2的子画法

证明：不失一般性，假定 $l_{2}^{D} (H_{1}) > 2$ ， $c r_{D} (H_{1}, H_{2}) = 3$ 且 $D (H_{i, i + 1})$ 与图6中的其中一个图同构。通过 $l_{2}^{D} (H_{1}) > 2$ ，可得到 $f_{D} (H_{1}) < 2$ 和 $f_{D} (H_{1, 2}) < 4$ 。

如果 $v_{1}^{4}$ 和 $v_{2}^{3}$ 位于 $D (H_{1})$ 的不同区域内，那么由引理2可知， $v_{1}^{3} v_{1}^{4}$ 交H₁一次，与 $f_{D} (H_{1}) < 2$ 矛盾，因此 $v_{1}^{4}$ 和 $v_{2}^{3}$ 位于 $D (H_{1})$ 的相同区域内。若 $v_{1}^{4}$ 在区域R₂内，则由引理2可知，路径 $v_{2}^{3} v_{1}^{4}$ 和 $v_{3}^{3} v_{1}^{4}$ 各交路径 $v_{1}^{1} v_{3}^{2} v_{1}^{3} v_{2}^{2}$ 一次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾，因此顶点 $v_{1}^{4}$ 不在区域R₂内，同理可证，顶点 $v_{1}^{4}$ 也不在区域R₃和R₄内，则顶点 $v_{1}^{4}$ 在区域R₀内。由于 $v_{2}^{4}$ 和 $v_{3}^{4}$ 与 $v_{1}^{4}$ 在同构意义下等价，与上述证明过程类似，可得到 $v_{2}^{4}$ 和 $v_{3}^{4}$ 也位于区域R₀内。证毕。

引理9令D是 $C_{2 k} \times K_{3}$ 的一个好的画法且 $l_{2}^{D} (H_{i}) > 1$ ，其中 $k \geq 3$ 。若 $c r_{D} (H_{i}, H_{i + 1}) = 3$ 且 $D (H_{i, i + 1})$ 与图6中的其中一个图同构，则 $c r_{D} (H_{i + 2}, H_{i, i + 1}) = 0$ ， $1 \leq i \leq 2 k$ 。

证明：反证法。不失一般性，假定 $l_{2}^{D} (H_{1}) > 2$ ， $c r_{D} (H_{1}, H_{2}) = 3$ 且 $D (H_{i, i + 1})$ 与图6中的其中一个图同构，有 $c r_{D} (H_{3}, H_{1, 2}) \geq 1$ 。通过 $l_{2}^{D} (H_{1}) > 2$ ，可得到 $f_{D} (H_{1}) < 2$ 和 $f_{D} (H_{1, 2}) < 4$ 。不失一般性，假设 $c r_{D} (v_{1}^{4} v_{2}^{3}, H_{1, 2}) \geq 1$ 。由于 $c r_{D} (H_{1}, H_{2}) = 3$ 且 $f_{D} (H_{1}) < 2$ ，可得 $c r_{D} (v_{1}^{4} v_{2}^{3}, H_{1}) = 0$ ，因此 $c r_{D} (v_{1}^{4} v_{2}^{3}, H_{2}) \geq 1$ 。又因为D是一个好的画法， $c r_{D} (v_{1}^{4} v_{2}^{3}, v_{3}^{2} v_{2}^{3} v_{1}^{2}) = 0$ ，因此 $c r_{D} (v_{1}^{4} v_{2}^{3}, v_{3}^{2} v_{1}^{3} v_{2}^{2} v_{3}^{3} v_{1}^{2}) \geq 1$ 。由引理8可知，顶点 $v_{1}^{4}$ 在区域R₀内。根据引理2可知，路径 $v_{1}^{4} v_{2}^{3}$ 交圈 $v_{2}^{1} v_{3}^{2} v_{1}^{3} v_{2}^{2} v_{3}^{3} v_{1}^{2} v_{2}^{1}$ 至少两次，与 $f_{D} (H_{1, 2}) < 4$ 矛盾。证毕。

引理10 令D是 $C_{2 k} \times K_{3}$ 的一个好的画法且 $l_{2}^{D} (H_{i}) > 1$ ，其中 $k \geq 3$ 。若 $D (H_{i})$ 与图1(c)同构，则 $l_{2}^{D} (H_{i}) \leq 3$ ， $1 \leq i \leq 2 k$ 。

证明：反证法。不失一般性，假设当 $D (H_{1})$ 同构于图1(c)时，有 $l_{2}^{D} (H_{1}) > 3$ 。通过 $l_{2}^{D} (H_{1}) > 3$ ，得到 $f_{D} (H_{1}) < 2$ ， $f_{D} (H_{1, 2}) < 4$ 和 $f_{D} (H_{1, 2, 3}) < 6$ 。我们分别考虑以下两种情况。

情况1 $v_{1}^{3}, v_{2}^{3}$ 和 $v_{3}^{3}$ 均在同一区域。

情况2 $v_{1}^{3}, v_{2}^{3}$ 和 $v_{3}^{3}$ 不在同一区域。

3. 结论

本文通过分支限界法证明了六边形图 $C_{2 k} \times K_{3} (k \geq 3)$ 的交叉数，并给出了相应的好的画法，确定了其交叉数的上界。进一步采用数学归纳法和反证法证明其交叉数的下界至少是4k，与假设矛盾，因此可以确定 $C_{2 k} \times K_{3} (k \geq 3)$ 的交叉数是4k，即 $c r (C_{2 k} \times K_{3}) = 4 k$ ， $k \geq 3$ 。对于不同的图，需要设计不同的分支限界策略才能对顶点数较大的图的交叉数进行计算。在得到对应的好的画法后，与数学证明相结合，最终才能确定给定图类的交叉数。进一步提出猜想： $c r (C_{6} \times K_{3}) = 7$ 。

参考文献

[1]	Bondy, J. and Murty, U. (1976) Graph Theory with Its Applications. American Elsevier, New York. https://doi.org/10.1007/978-1-349-03521-2
[2]	Clancy, K., Haythorpe, M. and Newcombe, A. (2020) A Survey of Graphs with Known or Bounded Crossing Numbers. The Electronic Journal of Combinatorics, 78, 209-296.
[3]	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
[4]	Garey, M.R. and Johnson, D.S. (1983) Crossing Number Is NP-Complete. SIAM Journal on Algebraic Discrete Methods, 4, 312-316. https://doi.org/10.1137/0604033
[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]	Schaefer, M. (2017) The Graph Crossing Number and Its Variant: A Survey. The Electronic Journal of Combinatorics, DS21. https://doi.org/10.37236/2713
[7]	Giambastiani, B.M.S. (2007) Evoluzione Idrologica ed Idrogeologica della Pineta di San Vitale (Ravenna). Ph.D. Thesis, Bologna University, Bologna.
[8]	Wang, J., Ouyang, Z. and Huang, Y. (2019) The Crossing Number of the Hexagonal Graph H3,n. Dis-cussiones Mathematicae Graph Theory, 39, 547-554. https://doi.org/10.7151/dmgt.2092
[9]	Zheng, W., Lin, X., Yang, Y. and Yang, X. (2008) The Crossing Number of Flower Snarks and Related Graphs. Ars Combinatoria, 86, 57-64.
[10]	林晓惠. 图论中若干难题的研究[D]: [博士学位论文]. 大连: 大连理工大学, 2004.

为你推荐

友情链接