本文未说明的概念和术语均同文献[1], 图$G=(V(G),E(G))$是简单连通图.两个点不相交的图$G$与$H$的联图, 用$G\vee H$表示, 是在$G$与$H$的并图中, 把$G$的每个顶点与$H$的每个顶点连接起来所得到的图.

一个图$G$画在平面上, 若满足如下条件:

(1) 任何两条相交叉的边最多交叉一次;

(2) 边不能自身交叉;

(3) 有相同端点的两条边不会交叉;

(4) 没有三条边交叉于同一点.

则称此画法为$G$的一个好画法.若图$G$的一个好画法用$D$表示, $G$中所有边与边的交叉数称为在画法$D$下$G$的交叉数, 用$cr_{D}(G)$表示.图$G$的交叉数定义为$cr(G)=\min\limits_{D}\{cr_{D}(G)\}$.若存在$G$的一个好画法$\phi$满足$cr_{\phi}(G)=cr(G)$, 则称$\phi$为$G$的一个最优画法.

图的交叉数是图的一个重要参数, 研究图的交叉数不仅具有重要的理论意义, 而且具有较强的现实意义, 如生物工程DNA的图示等.然而, 确定图的交叉数是一个NP-完全问题^[2].因其难度, 目前只知道一些特殊图类的交叉数, 如完全2部图^[3], 循环图^[4]等.关于完全二部图$K_{m,n}$的交叉数, Kleitman ^[3]得到了

$cr(K_{m,n})=Z(m,n)=\lfloor \frac{m}{2} \rfloor \lfloor \frac{m-1}{2} \rfloor\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor,m\leq 6,m\leq n.$

关于图$G$与圈图$C_{n}$联图的交叉数的研究, 2007年唐玲^[5]研究了$P_{m}$与$C_{n}$, $C_{m}$与$C_{n}$的联图交叉数, 2010年Klesc ^[6]得到了一个特殊六阶图与圈$C_{n}$联图的交叉数, 2011年王晶^[7]和袁秀华^[8]分别得到了$S_{m}\vee C_{n}(m=3,4$) 与$K_{2,3}\vee C_{n}$的交叉数.最近, Klesc ^[9]给出了两个特殊的五阶图与圈$C_{n}$的联图的交叉数.本文继续对五阶图与圈图的联图交叉数进行研究.在已知完全图$K_{5,n}$与联图$W_{4}\vee P_{n}$的交叉数的基础上, 利用假设法和比较法等方法, 得到了$cr(W_{4}\vee C_{n})$的交叉数为$Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+4, n\geq 3$.

为了方便, 我们对$W_{4}\vee C_{n}$作如下标记:设$V(W_{4})=\{t_{1}, t_{2}, t_{3}, t_{4}, t_{5}\}, V(C_{n})=\{y_{1},y_{2},\cdots ,y_{n}\}, $用$W_{4}$表示$W_{4}$的边导出子图, $T^{i}$表示$t_{i}$与顶点$y_{1}, y_{2}, \cdots ,y_{n}$所连的边导出子图, $i=1, 2, 3, 4, 5$.则有$W_{4}\vee C_{n}=W_{4}\cup (\bigcup\limits_{i=1}^{5}T^{i})\cup C_{n}$.

首先我们解释有关记号.设$D$是图$G$的一个好画法, 若$A$为$G$的边子集, 则$cr_{D}(A)$表示在画法$D$下由$A$中的边与边产生交叉的个数.若$A=E(G)$, 则$cr_{D}(A)$与$cr_{D}(G)$可看作是等同的.若$A$, $B$是图$G$的两个边子集, 则$cr_{D}(A, B)$表示$A$的边集和$B$的边集在画法$D$下的交叉数.显然, 当$A=B$时, $cr_{D}(A,A)=cr_{D}(A)$.由交叉数的定义及记号的意义, 易得到下面的性质:

性质2.1 若$D$为图$G$的一个好画法, 且$A, B, C$为$G$的边互不相交的边子集, 则

(1) $cr_{D}(A\cup B)=cr_{D}(A)+ cr_{D}(B)+ cr_{D}(A, B)$;

(2) $cr_{D}(A\cup B, C)=cr_{D}(A, C)+ cr_{D}(B, C)$.

性质2.2 (1) 若$H$是$G$的子图, 则$cr(H)\leq cr(G)$;

(2) 设$D$是$G$的一个好画法, 则$cr(G)\leq cr_{D}(G)$;

(3) 设$H_{1}$与$H_{2}$均为$G$的子图, 且$H_{1}\subseteq H_{2}$, 则$cr_{D}(H_{1})\leq cr_{D}(H_{2})$.

引理2.3^[5] 若$D$为图$G\vee C_{n}$的一个最优画法, 则$cr_{D}(C_{n})=0$.

引理2.4^[6] 设$D$为$mK_{1}\vee C_{n}$的一个好画法.若$C_{n}$自身不交叉, 且$C_{n}$的边不与其他边相交叉, 则对任意两个不同的子图$T^{i}$与$T^{j}$, 均有$cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor.$

引理2.5^[10] $cr(W_{4}\vee nK_{1})=Z(5,n)+n+\lfloor \frac{n}{2} \rfloor, n\geq 1.$

引理2.6^[11] $cr(W_{4}\vee P_{n})=Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+1, n\geq 2$.

定理3.1 $cr(W_{4}\vee C_{n})=Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+4, n\geq 3$.

证 首先构造$W_{4}\vee C_{n}$的一个好画法 (如图 1所示), 通过计数可以得到$cr(W_{4}\vee C_{n})\leq Z(5,n)+ n+\lfloor \frac{n}{2} \rfloor+4.$

下面证明对$W_{4}\vee C_{n}$的任意好画法$\phi$, 都有$cr_{\phi}(W_{4}\vee C_{n})\geq Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+4$.假设存在$W_{4}\vee C_{n}$的一个最优画法$D$, 使得

$cr_{D}(W_{4}\vee C_{n})\leq Z(5,n)+n +\lfloor \frac{n}{2} \rfloor+3.$

(3.1)

由于$W_{4}\vee C_{n}=W_{4}\cup (\bigcup\limits_{i=1}^{5}T^{i})\cup C_{n}$, 且$W_{4}\cup \bigcup\limits_{i=1}^{5}T^{i}$同构于$W_{4}\vee nK_{1}$, 由引理2.5及性质2.2知$cr_{D}(W_{4}\vee nK_{1})\geq cr(W_{4}\vee nK_{1})= Z(5,n)+n+\lfloor \frac{n}{2} \rfloor$.由引理2.3知$cr_{D}(C_{n})=0$, 因此结合性质2.1, 有

$cr_{D}(W_{4}\vee C_{n})=cr_{D}(W_{4}\vee nK_{1})+cr_{D}(C_{n}, W_{4}\cup \mathop \cup \limits_{i = 1}^5 T^{i})+cr_{D}(C_{n})\nonumber\\ \geq Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+cr_{D}(C_{n}, W_{4}\cup \mathop \cup \limits_{i = 1}^5 T^{i}).$

(3.2)

首先若$cr_{D}(C_{n}, W_{4}\cup \bigcup\limits_{i=1}^{5}T^{i})=0$.则$C_{n}$的边不与其他边交叉, 且$C_{n}$自身不交叉.因此根据引理2.4, 有$cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$.且连接$W_{4}$的各边, 则$W_{4}$至少与$\bigcup\limits_{i=1}^{5}T^{i}$产生$n+4\lfloor \frac{n}{2} \rfloor$个交叉.因此, 有

$cr_{D}(W_{4}\vee C_{n})\geq cr_{D}(\mathop \cup \limits_{i = 1}^5 T^{i})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ \geq C_{5}^{2}\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+ n+4\lfloor \frac{n}{2} \rfloor >Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

其次, 若$cr_{D}(C_{n}, W_{4}\cup \bigcup\limits_{i=1}^{5}T^{i})=1$.因为$W_{4}$为3-连通图 (则$cr_{D}(C_{n}, W_{4})\geq 3$), 所以只可能是$cr_{D}(C_{n}, \bigcup\limits_{i=1}^{5}T^{i})=1$.删除$C_{n}$中的与$\bigcup\limits_{i=1}^{5}T^{i}$相交叉的那条边, 则得到的图同胚于$W_{4}\vee P_{n}$, 且此时有$cr_{D}(W_{4}\vee P_{n})\leq Z(5,n)+n+\lfloor \frac{n}{2} \rfloor.$显然与引理2.6矛盾.

因此根据上述情况及式 (3.1) 与式 (3.2), 只可能有$2\leq cr_{D}(C_{n}, W_{4}\cup \bigcup\limits_{i=1}^{5}T^{i})\leq 3$.下面我们分两种情况进行讨论:

情况1 $cr_{D}(C_{n}, W_{4}\cup \bigcup\limits_{i=1}^{5}T^{i})=2$.

因为$W_{4}$为3-连通图 ($cr_{D}(C_{n},W_{4})\geq 3$), 所以只可能是$cr_{D}(C_{n},\bigcup\limits_{i=1}^{5}T^{i})= 2$.下面分两种子情况讨论:

情况1.1 存在一点, 不妨设为$t_{5}$, 满足$cr_{D}(C_{n}, T^{5})=2$.根据已知条件, $t_{i}(1\leq i\leq 5)$均位于$C_{n}$的同一区域, 不妨设为$C_{n}$的外部区域, 且从$t_{i}$的区域向左、向右分别将点标记为点$y_{k}$和$y_{k}^{,}$. $T^{i}(i\in \{1,2,3,4 \})$将外部区域分成$n$个子区域, $T^{5}$至少与$T^{i}$产生

$\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor-(\lfloor \frac{n}{2}\rfloor-1)-(\lceil \frac{n}{2}\rceil-1)= \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$

个交叉 (如图 2 (a)所示).对$1\leq i< j\leq 4$, 根据引理2.4有$cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$.连接$W_{4}$的各边, 则$W_{4}$至少与$\bigcup\limits_{i=1}^{5}T^{i}$产生$n+4\lfloor \frac{n}{2} \rfloor$个交叉.因此结合性质2.1有

$cr_{D}(W_{4}\vee C_{n})\geq cr_{D}(\bigcup\limits_{i = 1}^5 {{T^i}} )+cr_{D}(C_{n}, T^{5})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ =\sum\limits_{1 \le i<j \le 4} cr_{D}(T^{i},T^{j})+\sum\limits_{1 \le i<j \le 4} cr_{D}(T^{i},T^{5})+cr_{D}(C_{n}, T^{5})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ \geq C_{4}^{2}\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+ 4\lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor+2+n+4\lfloor \frac{n}{2} \rfloor\\ >Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

情况1.2 存在两点, 不妨设为$t_{4}, t_{5}$, 满足$cr_{D}(C_{n}, T^{4})=1, cr_{D}(C_{n}, T^{5})=1$.设$t_{i}(1\leq i\leq 5)$均位于$C_{n}$的外部区域, 且$y_{k}$和$y_{k}^{,}$向左、向右标记与情形1.1相同, 如图 2 (b)所示.对$T^{i}$与$T^{j}$的交叉数的计算分为如下3种情形考虑:

(1) 当$cr_{D}(C_{n}, T^{i})=0, cr_{D}(C_{n}, T^{j})=0$时, $cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$.

(2) 当$cr_{D}(C_{n}, T^{i})=0, cr_{D}(C_{n}, T^{j})=1$时, $cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor$.

(3) 当$cr_{D}(C_{n}, T^{4})=1, cr_{D}(C_{n}, T^{5})=1$时, $cr_{D}(T^{4}, T^{5})\geq \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$.

同理, 连接$W_{4}$的各边, 则$W_{4}$至少与$\bigcup\limits_{i=1}^{5}T^{i}$产生$n+4\lfloor \frac{n}{2} \rfloor$个交叉.因此有

$cr_{D}(W_{4}\vee C_{n})\geq cr_{D}(\mathop \cup \limits_{i = 1}^5 T^{i})+cr_{D}(C_{n}, T^{4})+cr_{D}(C_{n}, T^{5})+ \mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ =\sum\limits_{1 \le i<j \le 3}cr_{D}(T^{i},T^{j})+\mathop \sum \limits_{i = 1}^3 cr_{D}(T^{i},T^{4})+ \mathop \sum \limits_{i = 1}^3 cr_{D}(T^{i},T^{5})\\ +cr_{D}(T^{4}, T^{5})+cr_{D}(C_{n}, T^{4})+cr_{D}(C_{n}, T^{5})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ \geq C_{3}^{2}\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+C_{4}^{2}\lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor+ \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor+2+n+4\lfloor \frac{n}{2} \rfloor\\ >Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

情况2 $cr_{D}(C_{n}, W_{4}\cup \bigcup\limits_{i=1}^{5}T^{i})=3$.

因为$W_{4}$为3-连通图 ($cr_{D}(C_{n},W_{4})\geq 3$), 所以只可能是$cr_{D}(C_{n},\bigcup\limits_{i=1}^{5}T^{i})=3$或$cr_{D}(C_{n}, W_{4})=3$.下面分四种子情况讨论:

情况2.1 存在一点, 不妨设为$t_{5}$, 满足$cr_{D}(C_{n}, T^{5})=3$.如图 3 (a)所示.则对$1\leq i< j\leq 4$, $cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$.当$T^{i}$将外部区域分成$n$个子区域, $T^{5}$至少与$T^{i}$产生$\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor-(\lfloor \frac{n}{2}\rfloor-1)- (\lceil \frac{n}{2}\rceil-1)-(\lceil \frac{n}{2}\rceil-2)=\lfloor \frac{n-3}{2} \rfloor \lfloor \frac{n-4}{2} \rfloor$个交叉.同理, $W_{4}$至少与$\bigcup\limits_{i=1}^{5}T^{i}$产生$n+4\lfloor \frac{n}{2} \rfloor$个交叉.因此有

$c{r_D}({W_4} \vee {C_n}) \ge c{r_D}(\bigcup\limits_{i = 1}^5 {{T^i}} ) + c{r_D}({C_n},{T^5}) + \sum\limits_{i = 1}^5 c {r_D}({T^i},{W_4})\\ =\sum\limits_{1 \le i <j \le 4} cr_{D}(T^{i},T^{j})+\mathop \sum \limits_{i = 1}^4 cr_{D}(T^{i},T^{5}) +cr_{D}(C_{n}, T^{5})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ \geq C_{4}^{2}\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+ 4\lfloor \frac{n-3}{2} \rfloor \lfloor \frac{n-4}{2} \rfloor+3+n+4\lfloor \frac{n}{2} \rfloor\\ >Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

情况2.2 存在两点, 不妨设为$t_{4}, t_{5}$, 满足$cr_{D}(C_{n}, T^{4})=1, cr_{D}(C_{n}, T^{5})=2.$如图 3 (b)所示.对$1\leq i< j\leq 3$, 有$cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$.当$T^{i}$将外部区域分成的$n$个子区域, $T^{4}$至少与$T^{i}$产生$\lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor$个交叉, $T^{5}$至少与$T^{i}$产生$\lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$个交叉, $i=1, 2, 3$. $T^{4}$至少与$T^{5}$产生$\lfloor \frac{n-3}{2} \rfloor \lfloor \frac{n-4}{2} \rfloor$个交叉.同理, $W_{4}$至少与$\bigcup\limits_{i=1}^{5}T^{i}$产生$n+4\lfloor \frac{n}{2} \rfloor$个交叉.因此, 有

$cr_{D}(W_{4}\vee C_{n})\geq cr_{D}(\mathop \cup \limits_{i = 1}^5 T^{i})+cr_{D}(C_{n}, T^{4})+cr_{D}(C_{n}, T^{5})+ \mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ =\sum\limits_{1 \le i <j \le 3} cr_{D}(T^{i},T^{j})+\mathop \sum \limits_{i = 1}^3 cr_{D}(T^{i},T^{4})+ \mathop \sum \limits_{i = 1}^3 cr_{D}(T^{i},T^{5})\\ +cr_{D}(C_{n}, T^{4})+cr_{D}(C_{n}, T^{5})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ \geq C_{3}^{2} \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+ 3\lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor+ 3\lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor\\ +\lfloor \frac{n-3}{2} \rfloor \lfloor \frac{n-4}{2} \rfloor+3+n+4\lfloor \frac{n}{2} \rfloor\\ >Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

情况2.3 存在三点, 不妨设为$t_{3}, t_{4}, t_{5}$, 满足$cr_{D}(C_{n}, T^{3})=1$, $cr_{D}(C_{n}, T^{4})=1$, $cr_{D}(C_{n}, T^{5})=1$.如图 3(c)所示.对$T^{1}$与$T^{2}$, 有$cr_{D}(T^{1}, T^{2})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$; 且$T^{i}(i=1,2)$与$T^{3}, T^{4}, T^{5}$分别产生至少$\lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor$个交叉; $T^{3}, T^{4}, T^{5}$之间两两产生至少$\lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$个交叉.同理, $W_{4}$至少与$\bigcup\limits_{i=1}^{5}T^{i}$产生$n+4\lfloor \frac{n}{2} \rfloor$个交叉.因此有

$cr_{D}(W_{4}\vee C_{n})\geq cr_{D}(\mathop \cup \limits_{i = 1}^5 T^{i})+cr_{D}(C_{n}, \mathop \cup \limits_{i = 3}^5 T^{i})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ =cr_{D}(T^{1},T^{2})+\sum\limits_{3 \le i \le 5} c {r_D}({T^1},{T^j})+\sum\limits_{3 \le i \le 5} c {r_D}({T^2},{T^j})\\ +\sum\limits_{3 \le i<j \le 5} {c{r_D}({T^i},{T^j})} +\sum\limits_{3 \le i \le 5} c {r_D}({C_n},{T^i})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})\\ \geq\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+ 6\lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor+ 3\lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor+3+n+4\lfloor \frac{n}{2} \rfloor\\ >Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

情况2.4 $cr_{D}(C_{n},W_{4})=3$. $C_{n}$将平面分成内外两个区域, 因为$W_{4}$为3-连通图, 所以$W_{4}$的1个顶点 (不妨设为$t_{5}$) 位于$C_{n}$的内部区域, 另外4个顶点位于外部区域.则对$1\leq i< j\leq 4$, $cr_{D}(T^{i}, T^{j})\geq \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor$. $W_{4}$与$\bigcup\limits_{i=1}^{5}T^{i}$至少产生$n$个交叉.因此有

$cr_{D}(W_{4}\vee C_{n})\geq cr_{D}(\mathop \cup \limits_{i = 1}^4 T^{i})+\mathop \sum \limits_{i = 1}^5 cr_{D}(T^{i}, W_{4})+cr_{D}(C_{n},W_{4})\\ \geq C_{4}^{2}\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor+n+3>Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+3,$

与假设矛盾.

由以上可得, $cr_{D}(W_{4}\vee C_{n})\geq Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+4$.且由图 1可以找到一个好画法$\varphi$, 使得$cr_{\varphi}(W_{4}\vee C_{n})=Z(5,n)+ n+\lfloor \frac{n}{2} \rfloor+4$.因此, 必有$cr(W_{4}\vee C_{n})=Z(5,n)+n+\lfloor \frac{n}{2} \rfloor+4$.定理得证.

若Zarankiewicz猜想对于$m\geq 6$均成立, 则对于$W_{m}\vee C_{n}$, 我们有如下猜想

猜想3.2 $cr(W_{m}\vee C_{n})=Z(m+1,n)+n+[2(m-4)+1]\lfloor \frac{n}{2} \rfloor+\lceil \frac{m}{2} \rceil+2, m\geq 5, n\geq 3$.