广义棱柱和补棱柱中的超欧拉图
|
摘要
对于一个图G,它的顶点标号为1,2,…,n,S_n是在{1,2,…,n}上的n次对称群,α∈S_n是一个置换,图G的α-广义棱柱,记作α(G),是指图G的2个复制,G_x和G_y,连同所有置换边(x_i,y_(α(i))(1≤i≤n)所构成的图.图G的补棱柱,记作G G,同构于由G和G的补图G的不交并,再加上一个连接G和G对应顶点的完美匹配构成的图.如果图G有一个生成欧拉子图,那么称G是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.
For a graph G with vertices labeled 1,2,丨,n,a permutation a in S_n,the symmetric group on { 1,2,丨,n},and the a-generalized prism over G,a(G),they consist of two copies of,G say Gxand Gy,along with the edges( x_i,y_(a(i))). The complementary prism GG is isomorphic to the graph that arises from the disjoint union of G and the complement G of G by adding a perfect matching joining corresponding pairs of vertices in G and G. A graph is called supereulerian if it has a spanning eulerian subgraph. This paper investigates the necessary and sufficient conditions for the generalized prisms and complementary prisms of the complete bipartite graphs,paths and circles to be supereulerian graphs.
For a graph G with vertices labeled 1,2,丨,n,a permutation a in S_n,the symmetric group on { 1,2,丨,n},and the a-generalized prism over G,a(G),they consist of two copies of,G say Gxand Gy,along with the edges( x_i,y_(a(i))). The complementary prism GG is isomorphic to the graph that arises from the disjoint union of G and the complement G of G by adding a perfect matching joining corresponding pairs of vertices in G and G. A graph is called supereulerian if it has a spanning eulerian subgraph. This paper investigates the necessary and sufficient conditions for the generalized prisms and complementary prisms of the complete bipartite graphs,paths and circles to be supereulerian graphs.
引文
[1]BONDY J A,MURTY U S R.Graph theory with applications[M].London:Macmillan,1976.
[2]CHARTRAND G,HARARY F.Planar permutation graphs[C]//Annales de l'IHP Probabilités et statistiques.Gauthier-Villars,1967,3(4):433-438.
[3]PIAZZA B L,RINGEISEN R D.Connectivity of generalized prisms over G[J].Discrete Applied Mathematics,1991,30(2/3):229-233.
[4]BOROWIECKI M.On theα-permutation graphs[J].Recent Advances in Graph Theory,Academia,Prague,1975:89-92.
[5]CHARTRAND G,FRECHEN J B.On the chromatic number of permutation graphs[J].Proof Techniques in Graph Theory,1969:21-24.
[6]ELLINGHAM M.Petersen subdivisions in some regular graphs[J].Congr Numer,1984,44:33-40.
[7]HEDETNIEMI S.On classes of graphs defined by special cutsets of lines[J].The Many Facets of Graph Theory,1969:171-189.
[8]LI XIAO-MIN,LI DENG-XIN,LAI HONG-JIAN.Spanning eulerian subgraphs in generalized prisms[J].Ars Combinatoria,2012,106:305-312.
[9]PIAZZA B L,STUECKLE S.On the cut frequency vector of permutation graphs[J].Congr Number,1985,49:143-145.
[10]RINGEISEN R D.On cycle permutation graphs[J].Discrete mathematics,1984,51(3):265-275.
[11]ZELINKA B.Edge-colorings of permutation graphs[J].Mat Casopis Sloven Akad Vied.,1973,23:193-198.
[12]KLEE V.Which generalized prisms admit H-circuits[M]//Graph Theory and Applications.Springer,Berlin,Heidelberg,1972:173-178.
[13]HAYNES T W,HENNING M A,SLATER P J,van der MERWE L C.The complementary product of two graphs[J].Bulletin of the Institute of Combinatorics and its Applications,2007,51:21-30.
[14]CAPPELLE M R,PENSO L,RAUTENBACH D.Recognizing some complementary products[J].Theoretical Computer Science,2014,521:1-7.
[15]DESORMEAUX W J,HAYNES T W.Restrained domination in complementary prisms[J].Utilitas Mathematica,2011,86:267-278.
[16]KATHIRESAN K M,AROCKIARAJ S.Wiener indices of generalized complementary prisms[J].Bull Inst Combin Appl,2010,59:31-45.
[17]PULLEYBLANK W R.A note on graphs spanned by eulerian graphs[J].Journal of Graph Theory,1979,3(3):309-310.
[18]CATLIN P A.A reduction method to find spanning eulerian subgraphs[J].Journal of Graph Theory,1988,12(1):29-44.
[2]CHARTRAND G,HARARY F.Planar permutation graphs[C]//Annales de l'IHP Probabilités et statistiques.Gauthier-Villars,1967,3(4):433-438.
[3]PIAZZA B L,RINGEISEN R D.Connectivity of generalized prisms over G[J].Discrete Applied Mathematics,1991,30(2/3):229-233.
[4]BOROWIECKI M.On theα-permutation graphs[J].Recent Advances in Graph Theory,Academia,Prague,1975:89-92.
[5]CHARTRAND G,FRECHEN J B.On the chromatic number of permutation graphs[J].Proof Techniques in Graph Theory,1969:21-24.
[6]ELLINGHAM M.Petersen subdivisions in some regular graphs[J].Congr Numer,1984,44:33-40.
[7]HEDETNIEMI S.On classes of graphs defined by special cutsets of lines[J].The Many Facets of Graph Theory,1969:171-189.
[8]LI XIAO-MIN,LI DENG-XIN,LAI HONG-JIAN.Spanning eulerian subgraphs in generalized prisms[J].Ars Combinatoria,2012,106:305-312.
[9]PIAZZA B L,STUECKLE S.On the cut frequency vector of permutation graphs[J].Congr Number,1985,49:143-145.
[10]RINGEISEN R D.On cycle permutation graphs[J].Discrete mathematics,1984,51(3):265-275.
[11]ZELINKA B.Edge-colorings of permutation graphs[J].Mat Casopis Sloven Akad Vied.,1973,23:193-198.
[12]KLEE V.Which generalized prisms admit H-circuits[M]//Graph Theory and Applications.Springer,Berlin,Heidelberg,1972:173-178.
[13]HAYNES T W,HENNING M A,SLATER P J,van der MERWE L C.The complementary product of two graphs[J].Bulletin of the Institute of Combinatorics and its Applications,2007,51:21-30.
[14]CAPPELLE M R,PENSO L,RAUTENBACH D.Recognizing some complementary products[J].Theoretical Computer Science,2014,521:1-7.
[15]DESORMEAUX W J,HAYNES T W.Restrained domination in complementary prisms[J].Utilitas Mathematica,2011,86:267-278.
[16]KATHIRESAN K M,AROCKIARAJ S.Wiener indices of generalized complementary prisms[J].Bull Inst Combin Appl,2010,59:31-45.
[17]PULLEYBLANK W R.A note on graphs spanned by eulerian graphs[J].Journal of Graph Theory,1979,3(3):309-310.
[18]CATLIN P A.A reduction method to find spanning eulerian subgraphs[J].Journal of Graph Theory,1988,12(1):29-44.