具有禁止诱导特殊短有向路的超欧拉有向图（英文）
|
摘要
D是严格有向图(无环与重弧),如果D有一个生成欧拉子有向图,则称D是超欧拉的.文章主要研究一个强有向图成为超欧拉的禁止诱导子有向图的图条件.如果H■D,V(H)={x_1,x_2,x_3,x_4}而且A(H)={(x_2,x_1),(x_3,x_2),(x_3,x_4)},则称H是有向路P'4;如果H■D,V(H)={x_1,x_2,x_3,x_4}而且A(H)={(x_1,x_2),(x_2,x_3),(x_4,x_3)},则称H是有向路P″4.定义了有向图类F(Γ,h),主要研究了当h'≥h_4(h″≥h_4)且h'_4(h″_4)是最小值时,每个有向图在F(P'_4,h')(F(P″_4,h″))中是超欧拉的.
A digraph D is supereulerian if D has a spanning eulerian subdigraph. We investigate forbidden induced subdigraph conditions for a strong digraph to be supereulerian. A digraph H is a P'_4 if H■D,V( H) = { x_1,x_2,x_3,x_4} and A( H) = {( x_2,x_1),( x_3,x_2),( x_3,x_4) }. A digraph H is a P″_4 if H■D,V( H) = { x_1,x_2,x_3,x_4} and A( H) = {( x_1,x_2),( x_2,x_3),( x_4,x_3) }. In this paper,we define the digraph family F( Γ,h). Additionally,we determine the smallest value h'_4( h″_4) such that for any h'( h″) no less than h'_4( h″_4),every digraph in F( P_4,h')( F( P_4,h″)) is supereulerian.
A digraph D is supereulerian if D has a spanning eulerian subdigraph. We investigate forbidden induced subdigraph conditions for a strong digraph to be supereulerian. A digraph H is a P'_4 if H■D,V( H) = { x_1,x_2,x_3,x_4} and A( H) = {( x_2,x_1),( x_3,x_2),( x_3,x_4) }. A digraph H is a P″_4 if H■D,V( H) = { x_1,x_2,x_3,x_4} and A( H) = {( x_1,x_2),( x_2,x_3),( x_4,x_3) }. In this paper,we define the digraph family F( Γ,h). Additionally,we determine the smallest value h'_4( h″_4) such that for any h'( h″) no less than h'_4( h″_4),every digraph in F( P_4,h')( F( P_4,h″)) is supereulerian.
引文
[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].London:Springer,2009.
[3]BOESCH F T,SUFFEL C,TINDELL R.The spanning subgraphs of eulerian graphs[J].J Graph Theory,1977,1(1):79-84.
[4]PULLEYBLANK W R.A note on graphs spanned by Eulerian graphs[J].J Graph Theory,1979,3(3):309-310.
[5]ALGEFARI M J,LAI H J.Supereulerian digraphs with large arc-strong connectivity[J].J Graph Theory,2016,81(4):393-402.
[6]ALGEFARI M J,ALSATAMI K A,LAI H J,et al.Supereulerian digraphs with given local structures[J].Inform Process Lett,2016,116(5):321-326.
[7]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Appl Math,2016,7(3):320-326.
[8]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].J Graph Theory,2015,79(1):8-20.
[9]HONG Y,LAI H J,LIU Q.Supereulerian digraphs[J].Disc Math,2014,330(6):87-95.
[10]HONG Y,LIU Q,LAI H J.Ore-type degree condition of supereulerian digraphs[J].Disc Math,2016,339(8):2042-2050.
[11]FAYDREE R,FLANDRIN E,GYJACEK Z.Claw-free graphs—A survey[J].Disc Math,1997,164(1-3):87-147.
[2]BANG-JENSEN J,GUTIN G.Digraphs theory,algorithms and applications[M].London:Springer,2009.
[3]BOESCH F T,SUFFEL C,TINDELL R.The spanning subgraphs of eulerian graphs[J].J Graph Theory,1977,1(1):79-84.
[4]PULLEYBLANK W R.A note on graphs spanned by Eulerian graphs[J].J Graph Theory,1979,3(3):309-310.
[5]ALGEFARI M J,LAI H J.Supereulerian digraphs with large arc-strong connectivity[J].J Graph Theory,2016,81(4):393-402.
[6]ALGEFARI M J,ALSATAMI K A,LAI H J,et al.Supereulerian digraphs with given local structures[J].Inform Process Lett,2016,116(5):321-326.
[7]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Appl Math,2016,7(3):320-326.
[8]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].J Graph Theory,2015,79(1):8-20.
[9]HONG Y,LAI H J,LIU Q.Supereulerian digraphs[J].Disc Math,2014,330(6):87-95.
[10]HONG Y,LIU Q,LAI H J.Ore-type degree condition of supereulerian digraphs[J].Disc Math,2016,339(8):2042-2050.
[11]FAYDREE R,FLANDRIN E,GYJACEK Z.Claw-free graphs—A survey[J].Disc Math,1997,164(1-3):87-147.