一类型超欧拉有向图
|
摘要
如果一个有向图D包含一个生成欧拉子有向图,那么称D是超欧拉图.Alsatami等人定义了两个有向图的2-和,并且给了两个有向图的2-和是超欧拉图的充分条件.论文将2-和的概念推广到了l-路和,同时给出了一些两个有向图的l-路和是超欧拉图的充分条件.
A directed graph D is supereulerian if D contains a spanning eulerian subdigraph.Alsatami et al.introduce the 2-sum of two digraphs,and present sufficient conditions for the 2-sum of two digraphs to be supereulerian.In this paper,we introduce the l-path sum of two digraphs as a generalization of the 2-sum.Moreover,several sufficient conditions for the l-path sum of two digraphs to be superulerian are proved.
A directed graph D is supereulerian if D contains a spanning eulerian subdigraph.Alsatami et al.introduce the 2-sum of two digraphs,and present sufficient conditions for the 2-sum of two digraphs to be supereulerian.In this paper,we introduce the l-path sum of two digraphs as a generalization of the 2-sum.Moreover,several sufficient conditions for the l-path sum of two digraphs to be superulerian are proved.
引文
[1]BONDY J A,MURTY U S R.Graph theory[M].New York:Springer,2008.
[2]BANG-JENSEN J,GUTIN G.Digraphs:theory,algorithms and applications[M].2nd Edition.London:Springer-Verlag,2009.
[3]BOESCH F T,SUFFEL C,TINDELL R.The spanning subgraphs of Eulerian graphs[J].Journal of Graph Theory,1977,1:79-84.
[4]PULLEYBLANK W R.A note on graphs spanned by Eulerian graphs[J].Journal of Graph Theory,1979,3:309-310.
[5]CATLIN P A.A reduction method to find spanning Eulerian subgraphs[J].Journal of Graph Theory,1988,12:29-44.
[6]LAI H J,LI H,SHAO Y H,et al.On 3-edge-connected supereulerian graphs[J].Graphs and Combinatorics,2011,27:207-214.
[7]CHEN Z H.Snarks,hypohamiltonian graphs and non-supereulerian graphs[J].Graphs and Combinatorics,2016,32:2267-2273.
[8]LI X M,LEI L,LAI H J.Supereulerian graphs and the petersen graphs[J].Acta Mathematica Sinica(English Series),2014,2:291-304.
[9]CATLIN P A.Supereulerian graphs:a survey[J].Journal of Graph Theory,1992,16:177-196.
[10]CHEN Z H,LAI H J.Reduction techniques for supereulerian graphs and related topics-a survey[C]//Combinatorics and Graph Theory’95,Hefei,World Scientific Publishing,River Edge,1995,1:53-69.
[11]LAI H J,SHAO Y H,YAN H Y.An update on supereulerian graphs[J].WSEAS Transactions on Mathematics,2013,12:926-940.
[12]ALGEFARI M J,ALSATAMI K A,LAI H J,et al.Supereulerian digraphs with given local structures[J].In-formation Processing Letters,2016,116:321-326.
[13]ALGEFARI M J,LAI H J.Supereulerian digraphs with large arc-strong connectivity[J].Journal of Graph Theory,2016,81:393-402.
[14]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79:8-20.
[15]GUTIN G.Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,54:311-317.
[16]HONG Y M,LAI H J,LIU Q H.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[17]GUTIN G.Cycles and paths in directed graphs[D].Tel Aviv-Yafo:School of Mathematics,Tel Aviv University,1993.
[18]ALSATAMI K A.A study on dicycles and Eulerian subdigraphs in digraphs[D].Morgantown:West Virginia University,2016.
[19]LEWIN M.On maximal cricuits in directed graphs[J].Journal of Combinatorial Theory,Series B,1975,18:175-179.
[20]THOMASSEN C.Hamiltonian-connected tournaments[J].Journal of Combinatorial Theory,Series B,1980,28:142-163.
[21]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Applied Mathematics,2016,7:320-326.
[2]BANG-JENSEN J,GUTIN G.Digraphs:theory,algorithms and applications[M].2nd Edition.London:Springer-Verlag,2009.
[3]BOESCH F T,SUFFEL C,TINDELL R.The spanning subgraphs of Eulerian graphs[J].Journal of Graph Theory,1977,1:79-84.
[4]PULLEYBLANK W R.A note on graphs spanned by Eulerian graphs[J].Journal of Graph Theory,1979,3:309-310.
[5]CATLIN P A.A reduction method to find spanning Eulerian subgraphs[J].Journal of Graph Theory,1988,12:29-44.
[6]LAI H J,LI H,SHAO Y H,et al.On 3-edge-connected supereulerian graphs[J].Graphs and Combinatorics,2011,27:207-214.
[7]CHEN Z H.Snarks,hypohamiltonian graphs and non-supereulerian graphs[J].Graphs and Combinatorics,2016,32:2267-2273.
[8]LI X M,LEI L,LAI H J.Supereulerian graphs and the petersen graphs[J].Acta Mathematica Sinica(English Series),2014,2:291-304.
[9]CATLIN P A.Supereulerian graphs:a survey[J].Journal of Graph Theory,1992,16:177-196.
[10]CHEN Z H,LAI H J.Reduction techniques for supereulerian graphs and related topics-a survey[C]//Combinatorics and Graph Theory’95,Hefei,World Scientific Publishing,River Edge,1995,1:53-69.
[11]LAI H J,SHAO Y H,YAN H Y.An update on supereulerian graphs[J].WSEAS Transactions on Mathematics,2013,12:926-940.
[12]ALGEFARI M J,ALSATAMI K A,LAI H J,et al.Supereulerian digraphs with given local structures[J].In-formation Processing Letters,2016,116:321-326.
[13]ALGEFARI M J,LAI H J.Supereulerian digraphs with large arc-strong connectivity[J].Journal of Graph Theory,2016,81:393-402.
[14]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79:8-20.
[15]GUTIN G.Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,54:311-317.
[16]HONG Y M,LAI H J,LIU Q H.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[17]GUTIN G.Cycles and paths in directed graphs[D].Tel Aviv-Yafo:School of Mathematics,Tel Aviv University,1993.
[18]ALSATAMI K A.A study on dicycles and Eulerian subdigraphs in digraphs[D].Morgantown:West Virginia University,2016.
[19]LEWIN M.On maximal cricuits in directed graphs[J].Journal of Combinatorial Theory,Series B,1975,18:175-179.
[20]THOMASSEN C.Hamiltonian-connected tournaments[J].Journal of Combinatorial Theory,Series B,1980,28:142-163.
[21]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Applied Mathematics,2016,7:320-326.