笛卡尔积有向图的欧拉覆盖数
|
摘要
如果有向图D包含一个生成欧拉子图,那么有向图D是超欧拉有向图;如果有向图D包含一个生成有向迹,那么有向图D是生成迹有向图。文章定义了有向图D的欧拉覆盖数并用符号ec(D)表示。此外,文章将证明ec(D_1)=1的强连通有向图D_1与ec(D_2)=2的有向图D2做笛卡尔积后的欧拉覆盖数。
A digraph D is supereulerian if D contains a spanning eulerian subdigraph,and is trailable if D contains a spanning ditrail. Let ec(D) denote the eulerian cover number of D. In this paper,we define the eulerian cover number of D. Moreover,the paper will prove the eulerian cover number of the cartesian product of strong digraph D_1 with ec(D_1)= 1 and the digraph D_2 with ec(D_2)= 2.
A digraph D is supereulerian if D contains a spanning eulerian subdigraph,and is trailable if D contains a spanning ditrail. Let ec(D) denote the eulerian cover number of D. In this paper,we define the eulerian cover number of D. Moreover,the paper will prove the eulerian cover number of the cartesian product of strong digraph D_1 with ec(D_1)= 1 and the digraph D_2 with ec(D_2)= 2.
引文
[1]J.A.Bondy and U.S.R.Murty,Graph Theory[M].New York:Springer,2008.
[2]J.Bang-Jensen and G.Gutin,Digraphs:Theory,Algorithms and Applications[M].Second Edition,Springer,2010.
[3]X.D.Zhang,J.Liu,K.A.Alsatami and H.-J.Lai,Supereulerian and Trailable Digraph Products[J].Submit.
[4]J.Bang-Jensen and A.Maddaloni,Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79(1):8-20.
[5]Y.Hong,H.-J.Lai,and Q.Liu,Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[6]G.Gutin,Cycles and paths in directed graphs[J].PhD thesis,School of Mathematics,Tel Aviv University,1993.
[7]G.Gutin,Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,54:311-317.
[8]W.R.Pulleyblank,A note on graphs spanned by Eulerian graphs[J].Journal of Graph Theory,1979,3:309-310.
[9]董畅畅,刘娟.超欧拉路可合并有向图及半完全有向图[J].新疆师范大学学报(自然科学版),2017,36(3):53-56.
[10]M.J.Algefari,K.A.Alsatami,H.-J.Lai and J.Liu,Supereulerian digraphs with given local Structures[J].Information Processing Letters,2016,116(5):321-326.
[11]P.A.Catlin,A reduction method to find spanning Eulerian subgraphs[J].Graph Theory,1988,12:29-44.
[12]R.Gould,Advances on the Hamiltonian Problem-A Survey[J].Graphs and Combinatorics,2003,19:7-52.
[13]K.A.Alsatami,X.D.Zhang,J.Liu and H.-J.Lai,On a class of supereulerian digraphs[J].Applied Mathematics,2016,7:320-326.
[2]J.Bang-Jensen and G.Gutin,Digraphs:Theory,Algorithms and Applications[M].Second Edition,Springer,2010.
[3]X.D.Zhang,J.Liu,K.A.Alsatami and H.-J.Lai,Supereulerian and Trailable Digraph Products[J].Submit.
[4]J.Bang-Jensen and A.Maddaloni,Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79(1):8-20.
[5]Y.Hong,H.-J.Lai,and Q.Liu,Supereulerian digraphs[J].Discrete Mathematics,2014,330:87-95.
[6]G.Gutin,Cycles and paths in directed graphs[J].PhD thesis,School of Mathematics,Tel Aviv University,1993.
[7]G.Gutin,Connected(g;f)-factors and supereulerian digraphs[J].Ars Combinatoria,2000,54:311-317.
[8]W.R.Pulleyblank,A note on graphs spanned by Eulerian graphs[J].Journal of Graph Theory,1979,3:309-310.
[9]董畅畅,刘娟.超欧拉路可合并有向图及半完全有向图[J].新疆师范大学学报(自然科学版),2017,36(3):53-56.
[10]M.J.Algefari,K.A.Alsatami,H.-J.Lai and J.Liu,Supereulerian digraphs with given local Structures[J].Information Processing Letters,2016,116(5):321-326.
[11]P.A.Catlin,A reduction method to find spanning Eulerian subgraphs[J].Graph Theory,1988,12:29-44.
[12]R.Gould,Advances on the Hamiltonian Problem-A Survey[J].Graphs and Combinatorics,2003,19:7-52.
[13]K.A.Alsatami,X.D.Zhang,J.Liu and H.-J.Lai,On a class of supereulerian digraphs[J].Applied Mathematics,2016,7:320-326.