一些交叉数为2的特殊联图
|
摘要
确定一个图的交叉数是NP-完全问题。结合图的交叉数来刻画图的特征,目前相关结果非常少,针对连通的因子图而言,交叉数为1的联图G_1∨G_2的充要条件已经被刻画。在文中,我们试图将结果推广,也考虑不连通的因子图,刻画了当v(G_1)=3且cr(G_1∨G_2)=2时因子图G_1和G_1需满足的充要条件。
Determining the crossing number of a given graph is NP-complete.There are few restricted results concerning characterizing the structure of graph by its crossing number.For joint graph G_1∨G_2 whose crossing number was one,the necessary and sufficient conditions of G_1 and G_2 were investigated.To further the study,connected graphs and disconnected graphs were considered in the paper,and the necessary and sufficient conditions for graphs G_1 and G_2 to satisfy when v(G_1)=3 and cr(G_1∨G_2)=2 were described.
Determining the crossing number of a given graph is NP-complete.There are few restricted results concerning characterizing the structure of graph by its crossing number.For joint graph G_1∨G_2 whose crossing number was one,the necessary and sufficient conditions of G_1 and G_2 were investigated.To further the study,connected graphs and disconnected graphs were considered in the paper,and the necessary and sufficient conditions for graphs G_1 and G_2 to satisfy when v(G_1)=3 and cr(G_1∨G_2)=2 were described.
引文
[1]BONDY J A,MURTY U S R.Graph theory[M].New York:Springer,2008.
[2]GAREY M R,JOHNSON D S.Crossing number is NP-complete[J].SIAM Journal on Algebraic Discrete Methods,1983,4:312-316.
[3]GETHNER E,HOGBEN L,LIDICKY B,et al.On crossing numbers of complete tripartite and balanced complete multipartite graphs[J].Journal of Graph Theory,2017,84:552-565.
[4]BOKAL D,OPOROWSKI B,RICHTER R B,et al.Characterizing 2-crossing-critical graphs[J].Advances in Applied Mathematics,2016,74:23-208.
[5]DVORAK Z,MOHAR B.Crossing numbers of Periodic graphs[J].Journal of Graph Theory,2016,83:34-43.
[6]MA D J,RN H,LU J J.The crossing number of the circular graph C(2m+2,m)[J].Discrete Mathematics,2005,304:88-93.
[7]TANG L,WANG J,HUANG Y Q.The crossing number of the join of Cmand Pn[J].Journal of Mathematical Combinatorics,2007,1:110-116.
[8]KLESC M.The join of graphs and crossing numbers[J].Electronic notes in Discrete Mathematics,2007,28:349-355.
[9]KLESC M,SCHROTTER S.The crossing numbers of join products of paths with graphs of order four[J].Discussiones Mathematicae Graph Theory,2011,31:321-331.
[10]KLESC M.The crossing numbers of join of the special graph on six vertices with path and cycle[J].Discrete Mathematics,2010,310:1475-1481.
[11]BEHZAD M,MAHMOODIAN S E.On topological invariants of the product of graphs[J].Canadian Mathematical Bulletin,1969,12:157-166.
[12]KLESC M,PETRILLOVA J.On Cartesian products with small crossing numbers[J].Carpathian Journal of Matlematics,2012,28:67-75.
[13]KULLI V R,MUDDEBIHAL M H.Characterizations of join graphs with crossing number zero[J].Far East Journal of Applied Math.,2001,5:87-97.
[14]王晶,欧阳章东,黄元秋.关于交叉数为1的联图[J].应用数学学报,2017,9:727-733.
[15]RICHTER R B,SIRAN J.The crossing number of K3,nin a surface[J].Journal of Graph Theory,1996,21:51-54.
[16]ASANO K.The crossing number of K1,3,nand K2,3,n[J].Journal of Graph Theory,1980,10:1-8.
[2]GAREY M R,JOHNSON D S.Crossing number is NP-complete[J].SIAM Journal on Algebraic Discrete Methods,1983,4:312-316.
[3]GETHNER E,HOGBEN L,LIDICKY B,et al.On crossing numbers of complete tripartite and balanced complete multipartite graphs[J].Journal of Graph Theory,2017,84:552-565.
[4]BOKAL D,OPOROWSKI B,RICHTER R B,et al.Characterizing 2-crossing-critical graphs[J].Advances in Applied Mathematics,2016,74:23-208.
[5]DVORAK Z,MOHAR B.Crossing numbers of Periodic graphs[J].Journal of Graph Theory,2016,83:34-43.
[6]MA D J,RN H,LU J J.The crossing number of the circular graph C(2m+2,m)[J].Discrete Mathematics,2005,304:88-93.
[7]TANG L,WANG J,HUANG Y Q.The crossing number of the join of Cmand Pn[J].Journal of Mathematical Combinatorics,2007,1:110-116.
[8]KLESC M.The join of graphs and crossing numbers[J].Electronic notes in Discrete Mathematics,2007,28:349-355.
[9]KLESC M,SCHROTTER S.The crossing numbers of join products of paths with graphs of order four[J].Discussiones Mathematicae Graph Theory,2011,31:321-331.
[10]KLESC M.The crossing numbers of join of the special graph on six vertices with path and cycle[J].Discrete Mathematics,2010,310:1475-1481.
[11]BEHZAD M,MAHMOODIAN S E.On topological invariants of the product of graphs[J].Canadian Mathematical Bulletin,1969,12:157-166.
[12]KLESC M,PETRILLOVA J.On Cartesian products with small crossing numbers[J].Carpathian Journal of Matlematics,2012,28:67-75.
[13]KULLI V R,MUDDEBIHAL M H.Characterizations of join graphs with crossing number zero[J].Far East Journal of Applied Math.,2001,5:87-97.
[14]王晶,欧阳章东,黄元秋.关于交叉数为1的联图[J].应用数学学报,2017,9:727-733.
[15]RICHTER R B,SIRAN J.The crossing number of K3,nin a surface[J].Journal of Graph Theory,1996,21:51-54.
[16]ASANO K.The crossing number of K1,3,nand K2,3,n[J].Journal of Graph Theory,1980,10:1-8.