岳为君, 黄元秋, 唐 玲



岳为君1, 黄元秋*1, 唐 玲2

(1. 湖南师范大学 数学与计算机科学学院, 湖南 长沙, 410081; 2. 中南林业科技大学 理学院, 湖南 长沙, 410004 )

画法; 交叉数; 联图; 圈

图1 图

1 基本性质和引理

在证明本文的主要结果之前, 先给出一些基本性质和引理.

首先, 由交叉数的定义, 易有如下性质:

2 定理的证明

定理1(1)的证明

定理1(2)的证明

定理1(3)的证明

图3 的一个好画法

以下证明总能得到一个与(1)式相矛盾的结论, 从而完成定理1(3)的证明.

根据性质1和断言1可得:

图4 情形2

图5 子情形3.1

图6 子情形3.2

[1] Bondy J A, Murty U S R. Graph Theory With Applications[M]. London: Macmilan, 1976.

[2] Garey M R, Johnson D S. Crossing number is NP-complete[J]. Slam J Algebric Discrete Methods, 1993, 4: 312—316.

[4] Ho P T. On the crossing number of some complete multipartite graphs[J]. Utilitas Mathematica, 2009, 79: 143—154.

[7] Klesc M. On the crossing number of Cartesian products of stars and paths or cycles[J]. Math Slovaca, 1991, 41: 113—120.

[8] Beineke L W, Ringeisen R D. On the crossing number of products of cycles and graphs of order four[J]. Graph Theory, 1980, 4: 145—155.

[10] Zarankiewicz K. On a Problem of P Turan Concerning Graphs[J]. Fund Math, 1954, 41: 137—145.

[11] Oporowski B, Zhao D. Coloring graphs with crossing[J]. Discrete Mathematics, 2009, 309: 2948—2951.

[13] Klesc M. The join of the graphs and crossing numbers[J]. Discrete Math, 2007, 28: 349—350.

YUE Wei-jun1, HUANG Yuan-qiu1, TANG Ling2

(1. Department of Mathematics, Hunan Normal University, Changsha 410081, China; 2. Department of Mathematics, Central South University of Forestry and Technology, Changsha 410004, China)

drawing; crossing number; join graph; cycle

10.3969/j.issn.1672-6146.2013.04.001

O 157.5

1672-6146(2013)04-0001-07

email: hyqq@hunnu.edu.cn.

email: yueweijun121@163.com.

2013-08-11

国家自然科学基金资助项目(11371133)

(责任编校:刘晓霞)