关于l-路和图的超欧拉性
|
摘要
令G_1和G_2是两个点不交的图,P1l和P2l分别是G_1和G_2中长为l的路,将P1l和P2l中的点分别对应重合,得到G_1和G_2-E P(2)l的并,称为G_1和G_2的l-路和,记作G_1P1l,P2lG_2。本文将介绍两个无向图的l-路和是超欧拉图、D-超欧拉图和T-超欧拉图的充分条件;以及特殊的,当l=1时,介绍两个无向图的2-和是超欧拉图、D-超欧拉图和T-超欧拉图的充分条件。通过对这些问题的讨论和证明,可以深入人们对关于超欧拉图在运算方面的认识和了解,以便在以后的研究和实际应用中更好地利用超欧拉的相关性质。
Let G_1 and G_2 be two vertex disjoint graphs,and then P1l and P2l are two paths of length in G_1 and G_2 respectively. The l-path-sum G_1P1 l,P2 lG_2 of G_1 and G_2 with base paths P1l and P2l is obtained from the union of G_1 and G_2-E(P2l) by identifying v2j and v2j for all j∈[0,l] respectively. In this paper,sufficient conditions in the l-pathsum of supereulerian,D-supereulerian and T-supereulerian are introduced. Especially when l = 1,sufficient conditions in the 2-path-sum of supereulerian,D-supereulerian and T-supereulerian are also talked about. By discussing and proving these problems,it is hoped that the nature of Supereulerian graphs can be further understood and put into better use in the future.
Let G_1 and G_2 be two vertex disjoint graphs,and then P1l and P2l are two paths of length in G_1 and G_2 respectively. The l-path-sum G_1P1 l,P2 lG_2 of G_1 and G_2 with base paths P1l and P2l is obtained from the union of G_1 and G_2-E(P2l) by identifying v2j and v2j for all j∈[0,l] respectively. In this paper,sufficient conditions in the l-pathsum of supereulerian,D-supereulerian and T-supereulerian are introduced. Especially when l = 1,sufficient conditions in the 2-path-sum of supereulerian,D-supereulerian and T-supereulerian are also talked about. By discussing and proving these problems,it is hoped that the nature of Supereulerian graphs can be further understood and put into better use in the future.
引文
[1]BONDY A J,MURTY U S R.Graph theory[M].New York:Springer-Verlag,2008.
[2]BANG-JENSEN J,GUTIN G.Digraphs:theory,algorithms and applications[M].Second Edition,Springer,2010.
[3]BOESCHF L T,SUFFEL C,TINDELL R.The spanning subgraphs of eulerian graphs[J].Journal of Graph Theory,1977,1(1):79-84.
[4]PULLEYBLANK W R.A note on graphs spanned by eulerian graphs[J].Journal of Graph Theory,1979,3(3):309-310.
[5]CATLIN P A.Supereulerian graphs:a survey[J].Journal of Graph Theory,1992,16(2):177-196.
[6]LAI H J,SHAO Y H,YAN H Y.An update on supereulerian graphs[J].World Scientific and Engineering Academy and Society Transaction on Mathematics,2013,12(9):926-940.
[7]CHEN Z H.Snarks,Hypohamiltonian Graphs and Non-supereulerian Graphs[J].Graphs and Combinatorics,2016,32(6):2267-2273.
[8]LI X M,LEI L,LAI H J.Supereulerian graphs and the Petersen graphs[J].Acta Mathematica Sinica(English Series),2014,30(2):291-304.
[9]LAI H J,LI H,SHAO Y H,et al.On 3-edge-connected supereulerian graphs[J].Graphs and Combinatorics,2011,27(2):207-214.
[10]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Applied Mathematics,2016,7(3):320-326.
[11]侯二静,牛兆宏.一类型超欧拉有向图[J].河南科学,2017,35(7):1022-1027.
[2]BANG-JENSEN J,GUTIN G.Digraphs:theory,algorithms and applications[M].Second Edition,Springer,2010.
[3]BOESCHF L T,SUFFEL C,TINDELL R.The spanning subgraphs of eulerian graphs[J].Journal of Graph Theory,1977,1(1):79-84.
[4]PULLEYBLANK W R.A note on graphs spanned by eulerian graphs[J].Journal of Graph Theory,1979,3(3):309-310.
[5]CATLIN P A.Supereulerian graphs:a survey[J].Journal of Graph Theory,1992,16(2):177-196.
[6]LAI H J,SHAO Y H,YAN H Y.An update on supereulerian graphs[J].World Scientific and Engineering Academy and Society Transaction on Mathematics,2013,12(9):926-940.
[7]CHEN Z H.Snarks,Hypohamiltonian Graphs and Non-supereulerian Graphs[J].Graphs and Combinatorics,2016,32(6):2267-2273.
[8]LI X M,LEI L,LAI H J.Supereulerian graphs and the Petersen graphs[J].Acta Mathematica Sinica(English Series),2014,30(2):291-304.
[9]LAI H J,LI H,SHAO Y H,et al.On 3-edge-connected supereulerian graphs[J].Graphs and Combinatorics,2011,27(2):207-214.
[10]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Applied Mathematics,2016,7(3):320-326.
[11]侯二静,牛兆宏.一类型超欧拉有向图[J].河南科学,2017,35(7):1022-1027.