期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

几个完全二部图去掉一条边的交叉数

Crossing Number of Several Complete Bipartite Graphs by Deleting One Edge
下载PDF
导出
摘要 用km,n表示完全二部图,用Km,n\e表示完全二部图km,n去掉一条边e,先建立Km,n\e的一个好画法得到其交叉数的上界,再证明这个上界确实是K3,n\e和K4,n\e的交叉数,K3,n\e的交叉数为z(3,n)-「n/2」+1,K4,n\e的交叉数为z(4,n)-「n/2」+1. Let km,ndenote the complete bipartite graph,and km,n\e denote the graph km,n obtained by deleting one edge.This paper finds out the upper bound of the crossing number by establishing a good drawing of km,n\e,then proves that this upper bound is the crossing number of k3,n\e and k4,n\e,and the crossing number of k3,n\e and k4,n\e is respectively z(3,n)-「n/2」+1 and z(4,n)-「n/2」+1.
作者 贺佩玲 罗志军 黄元秋
机构地区 湖南人文科技学院数学系 湖南师范大学数计院
出处 《河南师范大学学报（自然科学版）》 CAS CSCD 北大核心 2011年第2期24-26,共3页 Journal of Henan Normal University(Natural Science Edition)
基金 湖南省教育厅课题(10C0831)
关键词 完全二部图 交叉数 画法 the complete bipartite graph crossing number drawing
分类号 N55 [自然科学总论] G658.3 [文化科学—教育学]
  • 相关文献

参考文献12

  • 1黄元秋,赵霆雷.关于完全3-部图K_(1,6,n)的交叉数[J].应用数学学报,2006,29(6):1046-1053. 被引量：9
  • 2Marian Klesc.The crossing numbers of products of 5-vertex graphs with paths and cycles. Discuss Math Graph Theory . 1999
  • 3Kzarankiewicz.On a problemof P.Turan concerning graphs. Found Math . 1954
  • 4Marian K.The crossing numbers of products of paths andstars with 4-vertex graphs. Journal of Graph Theory . 1994
  • 5Guy,R.K.The decline and fall of Zarankiewic‘s theorem. Proc.Proof Techniques in Graph Theory . 1969
  • 6Marian K.On the crossing number of Cartesian productsof stars and paths or cycles. Mathematica Slovaca . 1991
  • 7Bondy JA,Murty USR.Graph theory with applications. . 1976
  • 8Klesc M.2,3</sub>×P<sub>n</sub> and K<sub>2,3</sub>×S<sub>n</sub>&amp;sid=Tatra Mountains Mathematical Publication&amp;aufirst=Klesc M');&#xA; ">The crossing numbers of K<sub>2,3</sub>×P<sub>n</sub> and K<sub>2,3</sub>×S<sub>n</sub>. Tatra Mountains Mathematical Publication . 1996
  • 9Marian Klesc.The crossing number of Cartesian products of paths with 5-vertex graphs. Discrete Mathematics . 2001
  • 10Kleitman,D.J.The crossing number of K5,n. Journal of Physical and Chemistry . 1970

二级参考文献19

  • 1Bondy J A,Muty U S R.Graph Theory with Appplication.London:Macmillan Press,1976
  • 2Turan P.A Note of Welcome.J.Graph Theory,1977,1:7-9
  • 3Zarankiewicz K.On a Problem of P.Turan Concerning Graphs.Found.Math.,1954,41:137-145
  • 4Guy R K.The Decline and Fall of Zarankiewicz's Theorem.In:F.Harary(ed.),Proof Techniques in Graph Theory.New York:Academic Press,1969,63-69
  • 5Garey M R,Johnson D S.Crossing Number is NP-complete.SIAM J.Algebraic Discrete Methods,1983,4:312-316
  • 6Beineke L W,Ringeisen R D.On the Crossing Numbers of Products of Cycles and Graphs of order Four.J.Graph Theory,1980,4:145-155
  • 7Klesc M.On the Crossing Number of Cartesian Products of Stars and Paths or Cycles.Math.Slovaca,1991,41:113-120
  • 8Klesc M.The Crossing Numbers of Products of Paths and Stars with 4-vertex Graphs.J.Graph Theory,1994,18:605-614
  • 9Klesc M.The Crossing Number of Certain Cartesian Products.Discuss.Math-Graph Theory,1995,15:5-10
  • 10Marian Klesc.The Crossing Numbers of Cartesian Products of Paths with 5-vertex Graphs.Discrete Mathematics,2001,233:353-359

共引文献8

河南师范大学学报（自然科学版）
2011年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部