有关树的联图的厚度
|
摘要
图G的厚度θ(G)是指图G分解为平面生成子图的最小数,它是度量图的平面性的重要指标.图的厚度不仅仅在理论上有着重要的研究价值,它在超大规模集成电路和网络设计中也有着重要的应用.研究了与树有关的3类联图的厚度,第1类是完全图与树,任意包含n个顶点的图与树的联图;第2类是完全二部图与树的联图;第3类是完全k(k≥3)部图与树的联图.
The thickness of the graph Gis the minimum number of the planar spanning subgraphs into which Gcan be decomposed.It is an important measure of the planarity of a graph.The thickness of the graph has important research value not only in theory,but also application to VLSI and network designs.In this paper,we studied the thickness of the join of tree and three kinds of graphs.They are the join of tree and the complete graph,the tree and the graphs contain nvertices.The join of the tree and the complete bipartite graph.The join of the tree and the complete k-partite graph(k≥3).
The thickness of the graph Gis the minimum number of the planar spanning subgraphs into which Gcan be decomposed.It is an important measure of the planarity of a graph.The thickness of the graph has important research value not only in theory,but also application to VLSI and network designs.In this paper,we studied the thickness of the join of tree and three kinds of graphs.They are the join of tree and the complete graph,the tree and the graphs contain nvertices.The join of the tree and the complete bipartite graph.The join of the tree and the complete k-partite graph(k≥3).
引文
[1] CHEN Y C,YANG Y.The Thickness of the Complete Multipartite Graphs and the Join of Graphs[J].Combin Optim,2017,34(1):194-202.doi:10.1007/s10878-016-0057-1
[2] TUTTE W T.The Thickness of a Araph[J].Indag Math,1963,25:567-577.doi:10.1016/s1385-7258(63)50055-9
[3] MANSELD A.Determining the Thickness of Graphs is NP-hard[J].Math Proc Cambridge Philos Sco,1983,93(9):9-23.doi:10.1017/s030500410006028x
[4] BEINEKE L W,HARARY F.On the Thickness of the Complete Graph[J].Bull Amer Math Soc,1964,70:618-620.doi:10.1090/s0002-9904-1964-11213-1
[5] ALEKSEEV V B,GONCHAKOV V S.The Thickness of an Arbitrary Complete Graph[J].Math Sbornik,1976,30(2):187-202.
[6] VASAK J M.The Thickness of the Complete Graph[J].Notices Amer Math Soc,1976,17(4):618-620.
[7] BONDY J A,MURTY U.Graph Theory[M].London:Springer,2008:359-372.
[8] BEINEKE L W,HARARY F,MOON J W.On the Thickness of the Complete Bipartite Graph[J].Proc Cambridge Philos.Soc,1964,60:1-5.doi:10.1017/S0305004100037385
[9] PORANEN T.A Simulated Annealing Algorithm for Determining the Thickness of a Graph[J].Inform Sci,2005,172:155-172.doi:10.1016/j.ins.2004.02.029
[10] YANG Y Y.A Note on the Thickness of Kl,m,n[J].Ars Combin,2014,117:349-351.
[11] PYBER L.Covering the Edges of a Connected Graph by Paths[J].J Combin Theory(B),1996,66:152-159.doi:10.1006/jctb.1996.0012
[2] TUTTE W T.The Thickness of a Araph[J].Indag Math,1963,25:567-577.doi:10.1016/s1385-7258(63)50055-9
[3] MANSELD A.Determining the Thickness of Graphs is NP-hard[J].Math Proc Cambridge Philos Sco,1983,93(9):9-23.doi:10.1017/s030500410006028x
[4] BEINEKE L W,HARARY F.On the Thickness of the Complete Graph[J].Bull Amer Math Soc,1964,70:618-620.doi:10.1090/s0002-9904-1964-11213-1
[5] ALEKSEEV V B,GONCHAKOV V S.The Thickness of an Arbitrary Complete Graph[J].Math Sbornik,1976,30(2):187-202.
[6] VASAK J M.The Thickness of the Complete Graph[J].Notices Amer Math Soc,1976,17(4):618-620.
[7] BONDY J A,MURTY U.Graph Theory[M].London:Springer,2008:359-372.
[8] BEINEKE L W,HARARY F,MOON J W.On the Thickness of the Complete Bipartite Graph[J].Proc Cambridge Philos.Soc,1964,60:1-5.doi:10.1017/S0305004100037385
[9] PORANEN T.A Simulated Annealing Algorithm for Determining the Thickness of a Graph[J].Inform Sci,2005,172:155-172.doi:10.1016/j.ins.2004.02.029
[10] YANG Y Y.A Note on the Thickness of Kl,m,n[J].Ars Combin,2014,117:349-351.
[11] PYBER L.Covering the Edges of a Connected Graph by Paths[J].J Combin Theory(B),1996,66:152-159.doi:10.1006/jctb.1996.0012