一类超欧拉有向图中的超欧拉bypass
|
摘要
设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.
Let D be a digraph and λ(D)be the arc-strong connectivity of D,α′(D)be the size of a maximummatching of D. In this paper we show that if a strong digraph D and λ(D)≥α′(D)≥5,then D contains a supereulerianbypass(i.e.,a subdigraph is obtained from a spanning eulerian subdigraph by reversing exactly one arc).
Let D be a digraph and λ(D)be the arc-strong connectivity of D,α′(D)be the size of a maximummatching of D. In this paper we show that if a strong digraph D and λ(D)≥α′(D)≥5,then D contains a supereulerianbypass(i.e.,a subdigraph is obtained from a spanning eulerian subdigraph by reversing exactly one arc).
引文
[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 ed.New York:Springer,2010.
[3]BANG-JENSEN J,GUTIN G,LI H.Sufficient conditions for a digraph to be Hamiltonian[J].Journal of Graph Theory,1996,22(2):181-187.
[4]DARBINYAN S K.A sufficient condition for the hamiltonian property of digraphs with large semi-degrees[DB/OL](2011-11-08)[2018-05-10].http://arxiv.org/pdf/1111.1843.
[5]GORDON V S,ORLOVICH Y L,POTTS C N,et al.Hamiltonian properties of locally connected graphs with bounded vertex degree[J].Discrete Applied Mathematics,2011,159:1759-1774.
[6]BANG-JENSEN J,GUO Y B,ANDERS Y.A new sufficient condition for a digraph to be Hamiltonian[J].Discrete Applied Mathematics,1999,95:61-72.
[7]BENHOCHINE A,CLARK L,KOHLER N,et al.On circuits and pancyclic line graphs[J].Journal of Graph Theory,1986,10:411-425.
[8]HAN L,LAI H J,XIONG L,et al.The Chvátal-Erd?s condition for supereulerian graphs and the Hamiltonian index[J].Discrete Mathematics,2010,310:2082-2090.
[9]CATLIN P A.Supereulerian graphs:a survey[J].Journal of Graph Theory,1992,16(2):177-196.
[10]LESNIAK-FOSTER L,WILLIAMSON J E.On spanning and dominating circuits in graphs[J].Candadian Mathematical Bulletin,1977,20:215-220.
[11]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79(1):8-20.
[12]HONG Y M,LAI H J,LIU Q H.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[13]ALSPACH B,REID K B,ROSELLE D P.Bypasses in asymmetric digraphs[J].Journal of Combinatorial Theory,1974,17(1):11-18.
[14]BENHOCHINE A,WOJDA A P.Bypasses in digraphs[J].Ars Combinatoria,1983,16:85-94.
[15]GUO Y B,VOLKMANN L.Bypaths in tournaments[J].Discrete Applied Mathematics,1997,79:127-135.
[16]GRUNBAUM B.Antidirected Hamiltonian paths in tournaments[J].Journal of Combinatorial Theory,1971,11:249-257.
[17]THOMASSEN C.On the number of Hamiltonian tournaments[J].Discrete Mathematics,1980,31:315-323.
[18]THOMASSEN C.Hamiltonian connected tounaments[J].Journal of Combinatorial Theory,1980,28:142-163.
[19]DARBINYAN S K,KARAPRTYAN I A.On Hamiltonian bypasses in one class of Hamiltonian digraphs[DB/OL].(2014-04-23)[2018-5-10].https://arxiv.org/abs/1404.5780.
[20]ALGEFARI M J,LAI H J.Supereulerian digraphs with large arc-strong connectivity[J].Journal of Graph Theory,2016,81(4):393-402.
[2]BANG-JENSEN J,GUTIN G.Digraphs:theory,algorithms and applications[M].2nd ed.New York:Springer,2010.
[3]BANG-JENSEN J,GUTIN G,LI H.Sufficient conditions for a digraph to be Hamiltonian[J].Journal of Graph Theory,1996,22(2):181-187.
[4]DARBINYAN S K.A sufficient condition for the hamiltonian property of digraphs with large semi-degrees[DB/OL](2011-11-08)[2018-05-10].http://arxiv.org/pdf/1111.1843.
[5]GORDON V S,ORLOVICH Y L,POTTS C N,et al.Hamiltonian properties of locally connected graphs with bounded vertex degree[J].Discrete Applied Mathematics,2011,159:1759-1774.
[6]BANG-JENSEN J,GUO Y B,ANDERS Y.A new sufficient condition for a digraph to be Hamiltonian[J].Discrete Applied Mathematics,1999,95:61-72.
[7]BENHOCHINE A,CLARK L,KOHLER N,et al.On circuits and pancyclic line graphs[J].Journal of Graph Theory,1986,10:411-425.
[8]HAN L,LAI H J,XIONG L,et al.The Chvátal-Erd?s condition for supereulerian graphs and the Hamiltonian index[J].Discrete Mathematics,2010,310:2082-2090.
[9]CATLIN P A.Supereulerian graphs:a survey[J].Journal of Graph Theory,1992,16(2):177-196.
[10]LESNIAK-FOSTER L,WILLIAMSON J E.On spanning and dominating circuits in graphs[J].Candadian Mathematical Bulletin,1977,20:215-220.
[11]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79(1):8-20.
[12]HONG Y M,LAI H J,LIU Q H.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[13]ALSPACH B,REID K B,ROSELLE D P.Bypasses in asymmetric digraphs[J].Journal of Combinatorial Theory,1974,17(1):11-18.
[14]BENHOCHINE A,WOJDA A P.Bypasses in digraphs[J].Ars Combinatoria,1983,16:85-94.
[15]GUO Y B,VOLKMANN L.Bypaths in tournaments[J].Discrete Applied Mathematics,1997,79:127-135.
[16]GRUNBAUM B.Antidirected Hamiltonian paths in tournaments[J].Journal of Combinatorial Theory,1971,11:249-257.
[17]THOMASSEN C.On the number of Hamiltonian tournaments[J].Discrete Mathematics,1980,31:315-323.
[18]THOMASSEN C.Hamiltonian connected tounaments[J].Journal of Combinatorial Theory,1980,28:142-163.
[19]DARBINYAN S K,KARAPRTYAN I A.On Hamiltonian bypasses in one class of Hamiltonian digraphs[DB/OL].(2014-04-23)[2018-5-10].https://arxiv.org/abs/1404.5780.
[20]ALGEFARI M J,LAI H J.Supereulerian digraphs with large arc-strong connectivity[J].Journal of Graph Theory,2016,81(4):393-402.