PDF《数学杂志》

Vol.

35 (

2015 ) No.

3 数学杂志J. of Math. (PRC) W4 ∨ Cn 的交叉数 苏振华

1 , 黄元秋

2 (1. 怀化学院数学系, 湖南 怀化 418008) (2. 湖南师范大学数学系, 湖南 长沙 410081) 摘要: 本文研究了五阶图与圈图的联图交叉数. 利用假设法和比较法等方法, 得到了 W4 ∨ Cn 的交叉数为 Z(5, n) + n + n

2 + 4, 并推广了联图交叉数的结果与方法. 关键词: 交叉数;

联图;

轮图;

画法 MR(2010) 主题分类号: 05C10;

05C38 中图分类号: O157.5 文献标识码: A 文章编号: 0255-7797(2015)03-0608-07

1 引言 本文未说明的概念和术语均同文献 [1], 图G=(V (G), E(G)) 是简单连通图. 两个点不 相交的图 G 与H的联图, 用G∨H表示, 是在 G 与H的并图中, 把G的每个顶点与 H 的 每个顶点连接起来所得到的图. 一个图 G 画在平面上, 若满足如下条件: (1) 任何两条相交叉的边最多交叉一次;

(2) 边不能自身交叉;

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

(4) 没有三条边交叉于同一点. 则称此画法为 G 的一个好画法. 若图 G 的一个好画法用 D 表示, G 中所有边与边的交叉数 称为在画法 D 下G的交叉数, 用crD(G) 表示. 图G的交叉数定义为 cr(G) = min D {crD(G)}. 若存在 G 的一个好画法 φ 满足 crφ(G) = cr(G), 则称 φ 为G的一个最优画法. 图的交叉数是图的一个重要参数, 研究图的交叉数不仅具有重要的理论意义, 而且具有 较强的现实意义, 如生物工程 DNA 的图示等. 然而, 确定图的交叉数是一个 NP - 完全问题 [2] . 因其难度, 目前只知道一些特殊图类的交叉数, 如完全

2 部图 [3] , 循环图 [4] 等. 关于完全 二部图 Km,n 的交叉数, Kleitman [3] 得到了 cr(Km,n) = Z(m, n) = m

2 m ?

1 2 n

2 n ?

1 2 , m ≤ 6, m ≤ n. 关于图 G 与圈图 Cn 联图的交叉数的研究,

2007 年唐玲 [5] 研究了 Pm 与Cn, Cm 与Cn 的联图交叉数,

2010 年Klesc [6] 得到了一个特殊六阶图与圈 Cn 联图的交叉数,

2011 年王晶 [7] 和袁秀华 [8] 分别得到了 Sm ∨ Cn(m = 3, 4) 与K2,3 ∨ Cn 的交叉数. 最近, Klesc [9] 给出 ? 收稿日期: 2012-10-23 接收日期: 2012-01-16 基金项目:湖南省教育厅科研资助项目 (11C0981). 作者简介: 苏振华 (1982C), 男, 湖南常德, 讲师, 主要研究方向: 图的交叉数及图的亏格. No.

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

609 了两个特殊的五阶图与圈 Cn 的联图的交叉数. 本文继续对五阶图与圈图的联图交叉数进行 研究. 在已知完全图 K5,n 与联图 W4 ∨ Pn 的交叉数的基础上, 利用假设法和比较法等方法, 得到了 cr(W4 ∨ Cn) 的交叉数为 Z(5, n) + n + n

2 + 4, n ≥ 3. 为了方便, 我们对 W4 ∨ Cn 作如下标记: 设V(W4) = {t1, t2, t3, t4, t5}, V (Cn) = {y1, y2,yn}, 用W4 表示 W4 的边导出子图, Ti 表示 ti 与顶点 y1, y2,yn 所连的 边导出子图, i = 1, 2, 3, 4, 5. 则有 W4 ∨ Cn = W4 ∪ (

5 i=1 Ti ) ∪ Cn.

2 相关性质与引理 首先我们解释有关记号. 设D是图 G 的一个好画法, 若A为G的边子集, 则crD(A) 表 示在画法 D 下由 A 中的边与边产生交叉的个数. 若A=E(G), 则crD(A) 与crD(G) 可看 作是等同的. 若A, B 是图 G 的两个边子集, 则crD(A, B) 表示 A 的边集和 B 的边集在画法 D 下的交叉数. 显然, 当A=B时, crD(A, A) = crD(A). 由交叉数的定义及记号的意义, 易 得到下面的性质: 性质 2.1 若D为图 G 的一个好画法, 且A, B, C 为G的边互不相交的边子集, 则(1) crD(A ∪ B) = crD(A) + crD(B) + crD(A, B);