超欧拉路可合并有向图及半完全有向图（英文）
|
摘要
令D是一个严格有向图(无环与重弧),如果D含有一个生成欧拉子有向图,则称D是超欧拉的。文章主要研究路可合并有向图与半完全有向图成为超欧拉的充要条件,利用最大闭迹去寻找矛盾的方法证明了如果一个有向图D是一个路可合并有向图或半完全有向图,则D是超欧拉有向图当且仅当D是强连通的。
A digraph D is supereulerian if D has a spanning eulerian subdigraph.In this paper,we give sufficient and necessary conditions involving path-mergeable digraphs and semicomplete digraphs to be supereulerian.The method of finding the contradiction by using the maximum closed ditrail is proved that if D is a path-mergeable digraph or a semicomplete digraph,then D is supereulerian if and only if D is strong.
A digraph D is supereulerian if D has a spanning eulerian subdigraph.In this paper,we give sufficient and necessary conditions involving path-mergeable digraphs and semicomplete digraphs to be supereulerian.The method of finding the contradiction by using the maximum closed ditrail is proved that if D is a path-mergeable digraph or a semicomplete digraph,then D is supereulerian if and only if D is strong.
引文
[1]K.A.Alsatami,X.D.Zhang,J.Liu,et al.On a class of supereulerian digraphs[J].Applied Mathematics.2016,(7):320-326.
[2]M.J.Algefari,H.-J.Lai.Supereulerian digraphs with large arc-strong connectivity[J].Journal of Graph Theory.2016,81(4):393-402.
[3]J.Bang-Jensen.Digraphs with the path-merging property[J].Journal of Graph Theory.1995,20(2):255-265.
[4]J.Bang-Jensen,G.Gutin.Digraphs:Theory,Algorithms and Applications[M].Second Edition,Springer-Verlag.London,2009.
[5]J.Bang-Jensen,J.Huang,E.Prisner.In-tournament digraphs[J].Journal of Combinatorics,Theory Serious B.1993,59(2):267-287.
[6]J.Bang-Jensen,A.Maddaloni.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory.2015,79(1):8-20.
[7]F.T.Boesch,C.Sffel,R.Tindell.The spanning subgraphs of eulerian graphs[J].Journal of Graph Theory.1977,(1):79-84.
[8]J.A.Bondy,U.S.R.Murty.Graph Theory[M],Springer-Verlag.New York,2008.
[9]G.Gutin.Cycles and paths in directed graphs[D].Ph D thesis,School of Mathematics,Tel Aviv University,1993.
[10]G.Gutin.Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria.2000,(54):311-317.
[11]Y.Hong,H.-J.Lai,Q.Liu.Supereulerian digraphs[J].Discrete Mathematics.2014,(330):87-95.
[12]Y.Hong,Q.Liu,H.-J.Lai.Ore-type degree condition of supereulerian digraphs[J].Discrete Mathematics.2016,(339):2042-2050.
[13]W.R.Pulleyblank.A note on graphs spanned by Eulerian graphs[J].Journal of Graph Theory.1979,(3):309-310.
[2]M.J.Algefari,H.-J.Lai.Supereulerian digraphs with large arc-strong connectivity[J].Journal of Graph Theory.2016,81(4):393-402.
[3]J.Bang-Jensen.Digraphs with the path-merging property[J].Journal of Graph Theory.1995,20(2):255-265.
[4]J.Bang-Jensen,G.Gutin.Digraphs:Theory,Algorithms and Applications[M].Second Edition,Springer-Verlag.London,2009.
[5]J.Bang-Jensen,J.Huang,E.Prisner.In-tournament digraphs[J].Journal of Combinatorics,Theory Serious B.1993,59(2):267-287.
[6]J.Bang-Jensen,A.Maddaloni.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory.2015,79(1):8-20.
[7]F.T.Boesch,C.Sffel,R.Tindell.The spanning subgraphs of eulerian graphs[J].Journal of Graph Theory.1977,(1):79-84.
[8]J.A.Bondy,U.S.R.Murty.Graph Theory[M],Springer-Verlag.New York,2008.
[9]G.Gutin.Cycles and paths in directed graphs[D].Ph D thesis,School of Mathematics,Tel Aviv University,1993.
[10]G.Gutin.Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria.2000,(54):311-317.
[11]Y.Hong,H.-J.Lai,Q.Liu.Supereulerian digraphs[J].Discrete Mathematics.2014,(330):87-95.
[12]Y.Hong,Q.Liu,H.-J.Lai.Ore-type degree condition of supereulerian digraphs[J].Discrete Mathematics.2016,(339):2042-2050.
[13]W.R.Pulleyblank.A note on graphs spanned by Eulerian graphs[J].Journal of Graph Theory.1979,(3):309-310.