PDF《数学杂志》

(2) crD(A ∪ B, C) = crD(A, C) + crD(B, C). 性质 2.2 (1) 若H是G的子图, 则cr(H) ≤ cr(G);

(2) 设D是G的一个好画法, 则cr(G) ≤ crD(G);

(3) 设H1 与H2 均为 G 的子图, 且H1 ? H2, 则crD(H1) ≤ crD(H2). 引理 2.3 [5] 若D为图 G ∨ Cn 的一个最优画法, 则crD(Cn) = 0. 引理 2.4 [6] 设D为mK1 ∨ Cn 的一个好画法. 若Cn 自身不交叉, 且Cn 的边不与其他 边相交叉, 则对任意两个不同的子图 Ti 与Tj , 均有 crD(Ti , Tj ) ≥ n

2 n?1

2 . 引理 2.5 [10] cr(W4 ∨ nK1) = Z(5, n) + n + n

2 , n ≥ 1. 引理 2.6 [11] cr(W4 ∨ Pn) = Z(5, n) + n + n

2 + 1, n ≥ 2.

3 主要结果 定理 3.1 cr(W4 ∨ Cn) = Z(5, n) + n + n

2 + 4, n ≥ 3. 证 首先构造 W4 ∨ Cn 的一个好画法 (如图

1 所示), 通过计数可以得到 cr(W4 ∨ Cn) ≤ Z(5, n) + n + n

2 + 4. 图1: W4 ∨ Cn 的一个好画法 下面证明对 W4 ∨ Cn 的任意好画法 φ, 都有 crφ(W4 ∨ Cn) ≥ Z(5, n) + n + n

2 + 4. 假设

610 数学杂志Vol.

35 存在 W4 ∨ Cn 的一个最优画法 D, 使得 crD(W4 ∨ Cn) ≤ Z(5, n) + n + n

2 + 3. (3.1) 由于 W4 ∨ Cn = W4 ∪ (

5 i=1 Ti ) ∪ Cn, 且W4 ∪

5 i=1 Ti 同构于 W4 ∨ nK1, 由引理 2.5 及性质 2.2 知crD(W4 ∨ nK1) ≥ cr(W4 ∨ nK1) = Z(5, n) + n + n

2 . 由引理 2.3 知crD(Cn) = 0, 因此结 合性质 2.1, 有crD(W4 ∨ Cn) = crD(W4 ∨ nK1) + crD(Cn, W4 ∪

5 i=1 Ti ) + crD(Cn) ≥ Z(5, n) + n + n

2 + crD(Cn, W4 ∪

5 i=1 Ti ). (3.2) 首先若 crD(Cn, W4 ∪

5 i=1 Ti ) = 0. 则Cn 的边不与其他边交叉, 且Cn 自身不交叉. 因 此根据引理 2.4, 有crD(Ti , Tj ) ≥ n

2 n?1

2 . 且连接 W4 的各边, 则W4 至少与

5 i=1 Ti 产生 n +

4 n

2 个交叉. 因此, 有crD(W4 ∨ Cn) ≥ crD(

5 i=1 Ti ) +

5 i=1 crD(Ti , W4) ≥ C2

5 n

2 n ?

1 2 + n +

4 n

2 > Z(5, n) + n + n

2 + 3, 与假设矛盾. 其次, 若crD(Cn, W4 ∪

5 i=1 Ti ) = 1. 因为 W4 为3-连通图 (则crD(Cn, W4) ≥ 3), 所以 只可能是 crD(Cn,

5 i=1 Ti ) = 1. 删除 Cn 中的与

5 i=1 Ti 相交叉的那条边, 则得到的图同胚于 W4 ∨ Pn, 且此时有 crD(W4 ∨ Pn) ≤ Z(5, n) + n + n

2 . 显然与引理 2.6 矛盾. 因此根据上述情况及式 (3.1) 与式 (3.2), 只可能有

2 ≤ crD(Cn, W4 ∪

5 i=1 Ti ) ≤ 3. 下面我 们分两种情况进行讨论: 情况

1 crD(Cn, W4 ∪

5 i=1 Ti ) = 2. 因为 W4 为3-连通图 (crD(Cn, W4) ≥ 3), 所以只可能是 crD(Cn,

5 i=1 Ti ) = 2. 下面分两 种子情况讨论: 情况 1.1 存在一点, 不妨设为 t5, 满足 crD(Cn, T5 ) = 2. 根据已知条件, ti(1 ≤ i ≤ 5) 均位于 Cn 的同一区域, 不妨设为 Cn 的外部区域, 且从 ti 的区域向左、 向右分别将点标记为 点yk 和y, k. Ti (i ∈ {1, 2, 3, 4}) 将外部区域分成 n 个子区域, T5 至少与 Ti 产生 n

2 n ?

1 2 ? ( n

2 ? 1) ? ( n

2 ? 1) = n ?

2 2 n ?

3 2 No.

3 苏振华等: W4 ∨ Cn 的交叉数

611 个交叉 (如图 2(a) 所示). 对1≤i