超欧拉和双有向迹的强积有向图
|
摘要
如果D是简单有向图(无自环与平行弧)并且包含一个生成欧拉子有向图,则称D是超欧拉有向图.如果D中存在2个不同的点x,y,使得D既有生成(x,y)-有向迹又有生成(y,x)-有向迹,则称D是双有向迹有向图.主要研究了关于2个有向图D1和D2的强积有向图成为超欧拉有向图或双有向迹有向图的充分条件.
A simple digraph D(without loops and parallel arcs) is super Eulerian if D contains a spanning Eulerian subdigraph,D is bi-trailable if there exist two distinct vertices x,y ∈V(D),such that D has both spanning(x,y)-ditrail and spanning(y,x)-ditrail. In this paper,we obtain the sufficient conditions on the strong product digraph D_1D_2 to be super Eulerian digraph or bi-trailable digraph.
A simple digraph D(without loops and parallel arcs) is super Eulerian if D contains a spanning Eulerian subdigraph,D is bi-trailable if there exist two distinct vertices x,y ∈V(D),such that D has both spanning(x,y)-ditrail and spanning(y,x)-ditrail. In this paper,we obtain the sufficient conditions on the strong product digraph D_1D_2 to be super Eulerian digraph or bi-trailable digraph.
引文
[1]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer-Verlag,2008.
[2]BANG-JENSEN J,GUTIN G.Digraphs:Theory Algorithms and Applications[M].2nd ed.New York:Springer-Verlag,2010.
[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]CATLIN P A.Supereulerian graphs:a survey[J].J Graph Theory,1992,16(2):177-196.
[6]CHEN Z H,LAI H J.Reduction techniques for super-Eulerian graphs and related topics:a survey[C]//Combinatorics and Graph Theory.New Jersey:World Science Citation Index Publishing,1995:53-69.
[7]LAI H J,SHAO Y,YAN H.An update on supereulerian graphs[J].World Scientific and Engineering Academy Society Transactions on Mathematics,2013,12(9):926-940.
[8]GUTIN G.Cycles and paths in directed graphs[D].Tel Aviv:Tel Aviv University,1993.
[9]GUTIN G.Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,52:311-317.
[10]ALGEFARI M J,ALSATAMI K A,LAI H J,et al.Supereulerian digraphs with given local structures[J].Information Processing Letters,2016,116(5):321-326.
[11]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].J Graph Theory,2015,79(1):8-20.
[12]HONG Y,LAI H J,LIU Q.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[13]GOULD R J.Advances on the Hamiltonian problem:a survey[J].Graphs and Combinatorics,2003,19:7-52.
[14]DONG C,LIU J,ZHANG X,et al.Supereulerian digraphs with given diameter[J].Appl Math Comput,2018,329:5-13.
[15]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Appl Math,2016,7(3):320-326.
[2]BANG-JENSEN J,GUTIN G.Digraphs:Theory Algorithms and Applications[M].2nd ed.New York:Springer-Verlag,2010.
[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]CATLIN P A.Supereulerian graphs:a survey[J].J Graph Theory,1992,16(2):177-196.
[6]CHEN Z H,LAI H J.Reduction techniques for super-Eulerian graphs and related topics:a survey[C]//Combinatorics and Graph Theory.New Jersey:World Science Citation Index Publishing,1995:53-69.
[7]LAI H J,SHAO Y,YAN H.An update on supereulerian graphs[J].World Scientific and Engineering Academy Society Transactions on Mathematics,2013,12(9):926-940.
[8]GUTIN G.Cycles and paths in directed graphs[D].Tel Aviv:Tel Aviv University,1993.
[9]GUTIN G.Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,52:311-317.
[10]ALGEFARI M J,ALSATAMI K A,LAI H J,et al.Supereulerian digraphs with given local structures[J].Information Processing Letters,2016,116(5):321-326.
[11]BANG-JENSEN J,MADDALONI A.Sufficient conditions for a digraph to be supereulerian[J].J Graph Theory,2015,79(1):8-20.
[12]HONG Y,LAI H J,LIU Q.Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[13]GOULD R J.Advances on the Hamiltonian problem:a survey[J].Graphs and Combinatorics,2003,19:7-52.
[14]DONG C,LIU J,ZHANG X,et al.Supereulerian digraphs with given diameter[J].Appl Math Comput,2018,329:5-13.
[15]ALSATAMI K A,ZHANG X D,LIU J,et al.On a class of supereulerian digraphs[J].Appl Math,2016,7(3):320-326.