期刊菜单

The Crossing Number of Rose Windows Graph R(3k, 3, 2)
DOI: 10.12677/PM.2023.1310304, PDF, HTML, XML, 下载: 127  浏览: 203

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.

1. 引言

1.1. 完全图Kn

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

$cr\left({K}_{n}\right)=Z\left(n\right)=\frac{1}{4}\frac{n}{2}\frac{n-1}{2}\frac{n-2}{2}\frac{n-3}{2}$ .

$cr\left({K}_{n}\right)\ge n\left(n-1\right)\left(n-2\right)\left(n-3\right)/80$ .

Richter等人 [6] [7] 证明了和 ${K}_{n}$${K}_{n-1}$ 之间的关系： $cr\left({K}_{n}\right)\ge ⌈\frac{n}{n-4}\cdot cr\left({K}_{n-1}\right)⌉$

1.2. 完全二部图Km,n

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

$cr\left({K}_{m,n}\right)=⌊\frac{m}{2}⌋⌊\frac{m-1}{2}⌋⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$ .

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

$cr\left({K}_{m,n}\right)\ge \frac{1}{5}m\left(m-1\right)⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+9.9×{10}^{-6}{m}^{2}{n}^{2}$ .

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

$cr\left({K}_{m,n}\right)\ge 0.8594Z\left(m,n\right).$

1.3. 广义Petersen图

$\left\{\begin{array}{l}cr\left(P\left(3h,3\right)\right)=h,h\ge 4,\\ cr\left(P\left(3h+1,3\right)\right)\ge h+3,h\ge 3,\\ cr\left(P\left(3h+2,3\right)\right)=h+2,h\ge 2.\end{array}$

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

$\left\{\begin{array}{l}cr\left(P\left(3h,3\right)\right)=h,h\ge 4,\\ cr\left(P\left(3h+1,3\right)\right)\ge h+3,h\ge 3,\\ cr\left(P\left(3h+2,3\right)\right)=h+2,h\ge 2.\end{array}$

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

$cr\left(GP\left(3k-1,k\right)\right)=k+1,$

$cr\left(GP\left(3k+1,k\right)\right)=k+3.$

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

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

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

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

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

Figure 1. A good drawing of with 3k crossings

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}\cdots {a}_{3k}$${P}_{j}={b}_{j}{b}_{j+3}\cdots {b}_{3k-3+j}$ ，其中 $1\le j\le 3$ ，对于路径P，如果 $a,b\in V\left(P\right)$ ，则 $aPv$ 表示P从a到b的连续顶点。

${a}_{3}$ 在区域 ${R}_{2}$ 中， ${b}_{1}{a}_{3}$ 干净，由引理1及 ${f}_{D}\left({H}_{1，2}\right)<2$${a}_{2}{a}_{3}$ 只能与 ${a}_{4}{b}_{4}$ 相交， $D\left({C}_{1}\cup {a}_{2}{a}_{3}\right)$ 同构于图2(b)，再由引理1可知，路径 ${a}_{4}{a}_{5}{b}_{5}{b}_{2}$ 与圈 ${a}_{1}{a}_{2}{a}_{3}{b}_{1}$ 相交一次，与 ${f}_{D}\left({H}_{1，2}\right)<2$ 相矛盾。

${a}_{3}$ 在区域 ${R}_{0}$ 中， ${b}_{1}{a}_{3}$ 干净，由引理1知 ${a}_{2}{a}_{3}$${a}_{4}{b}_{4}$ 相交至少相交两次，而D是一个好的画法，因此 ${a}_{2}{a}_{3}$ 干净， $D\left({C}_{1}\cup {a}_{2}{a}_{3}\cup {b}_{1}{a}_{3}\right)$ 同构于图2(c)，根据引理1可知，路径 ${a}_{4}{a}_{5}{b}_{3}{b}_{3k}{a}_{3k}{a}_{3k-1}{b}_{3k-1}{b}_{2}$${b}_{4}{b}_{7}{a}_{7}{b}_{5}{b}_{2}$${a}_{1}{a}_{2}{a}_{3}{b}_{1}$ 相交，与 ${f}_{D}\left({H}_{1，2}\right)<2$ 相矛盾。

(a) (b) (c)

Figure 2. Subdrawings of D

${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}\left({H}_{1}\right)<1$ 相矛盾。

${a}_{3}$ 在区域 ${R}_{0}$ 中， ${b}_{1}{a}_{3}$ 干净，此时有 ${f}_{D}\left({H}_{1,4}\right)\ge 1$ ，考虑 ${a}_{2}{a}_{3}$ ，由 ${f}_{D}\left({H}_{1,4}\right)<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\left({C}_{1}\cup {a}_{2}{a}_{3}\cup {b}_{1}{a}_{3}\right)$ 同构于图3(b)，此时有 ${f}_{D}\left({H}_{1,2}\right)\ge 1.5$ ，根据引理1可知，路径 ${b}_{4}{a}_{6}{a}_{5}{a}_{4}$ 与圈 ${b}_{1}{a}_{1}{a}_{2}{a}_{3}$ 相交，与 ${f}_{D}\left({H}_{1,2}\right)<2$ 相矛盾。

${a}_{2}{a}_{3}$${a}_{4}{b}_{4}$ 相交，则 $D\left({C}_{1}\cup {a}_{2}{a}_{3}\cup {b}_{1}{a}_{3}\right)$ 同构于图3(c)，根据引理1可知，路径 ${a}_{1}{a}_{3k}{b}_{3k}{a}_{2}$${a}_{1}{b}_{3k-1}{b}_{2}$${C}_{1}\cup {b}_{1}{a}_{3}\cup {a}_{2}{a}_{3}$ 相交，此时有 ${f}_{D}\left({H}_{1，4}\right)\ge 3$ ，考虑 ${b}_{2}{b}_{5}$ ，由 ${f}_{D}\left({H}_{1,4}\right)<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}\left({H}_{1,4}\right)<4$ 相矛盾。

${b}_{5}\in {R}_{3}$${b}_{2}{b}_{5}$ 干净，此时由 ${f}_{D}\left({H}_{1,4}\right)\ge 3$ 可知 ${a}_{3}{a}_{4}$ 是干净的， $D\left({C}_{1}\cup {b}_{1}{a}_{3}\cup {a}_{2}{a}_{3}\cup {a}_{3}{a}_{4}\cup {b}_{2}{b}_{5}\right)$ 同构于图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\left({C}_{1,2}\cup {a}_{3}{a}_{4}\right)$ 同构于图3(e)、图3(f)、图3(g)和图3(h)。

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

Figure 3. Subdrawings of D

${a}_{2}{a}_{3}$ 同时与 ${a}_{4}{b}_{2}$${a}_{4}{b}_{4}$ 相交，根据引理1，此时与 ${f}_{D}\left({H}_{1,2}\right)<2$ 相矛盾。

${a}_{2}{a}_{3}$ 干净，则 $D\left({C}_{1}\cup {b}_{1}{a}_{3}\cup {a}_{2}{a}_{3}\right)$ 同构于图3(j)，此时根据引理1有路径 ${b}_{4}{a}_{6}{a}_{5}{a}_{4}$${b}_{4}{P}_{1}{b}_{3k-2}{b}_{1}{a}_{3}{a}_{4}$ 和圈 ${a}_{1}{a}_{2}{a}_{3}{b}_{1}$ 相交，此时 ${f}_{D}\left({H}_{1,2}\right)\ge 1.5$ ，因此在画法D下 ${H}_{1,2}$ 的其他边干净，故 ${a}_{3}{a}_{4}$ 也是干净的， $D\left({C}_{1}\cup {b}_{1}{a}_{3}\cup {a}_{2}{a}_{3}\cup {a}_{3}{a}_{4}\right)$ 同构于图3(k)。根据引理1可知，路径 ${b}_{2}{b}_{5}{a}_{7}{b}_{7}{P}_{1}{b}_{3k-2}{b}_{1}$${b}_{2}{b}_{3k-1}{a}_{1}$${a}_{1}{a}_{3k}{b}_{3k}{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}\left({H}_{1,4}\right)\ge 3$ ，考虑路径 ${b}_{2}{b}_{5}{a}_{7}{b}_{7}{P}_{1}{b}_{3k-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}\left({H}_{1,4}\right)\ge 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}_{3k-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}\left({H}_{1,4}\right)\ge 3.5$ ，因此在画法D下 ${H}_{1,4}$ 的其他边干净；同理考虑路径 ${b}_{4}{a}_{6}{a}_{5}{a}_{4}$ 中的边 ${b}_{4}{a}_{6}$${a}_{4}{a}_{5}$ ，由 ${f}_{D}\left({H}_{1,4}\right)\ge 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}\left({H}_{1,4}\right)<4$ 相矛盾。证毕。

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, 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.