Geodesic
Dominated pair degree sum conditions of supereulerian digraphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 879-891 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A digraph D is supereulerian if D contains a spanning eulerian subdigraph. In this paper, we propose the following problem: is there an integer t with 0≤ t≤ n-3 so that any strong digraph with n vertices satisfying either both d(u) ≥ n -1+ t and d(v) ≥ n-2- t or both d(u) ≥ n-2- t and d(v) ≥ n -1+ t, for any pair of dominated or dominating nonadjacent vertices {u, v}, is supereulerian? We prove the cases when t=0,t=n-4 and t=n-3. Moreover, we show that if a strong digraph D with n vertices satisfies min{d^+(u) + d^- (v), d^- (u) + d^+(v)}≥ n-1 for any pair of dominated or dominating nonadjacent vertices {u,v} of D, then D is supereulerian.
Keywords: supereulerian digraph, spanning eulerian subdigraph, dominated pair degree sum condition 
@article{DMGT_2024_44_3_a3,
     author = {Dong, Changchang and Meng, Jixiang and Liu, Juan},
     title = {Dominated pair degree sum conditions of supereulerian digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {879--891},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a3/}
}
TY  - JOUR
AU  - Dong, Changchang
AU  - Meng, Jixiang
AU  - Liu, Juan
TI  - Dominated pair degree sum conditions of supereulerian digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 879
EP  - 891
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a3/
LA  - en
ID  - DMGT_2024_44_3_a3
ER  - 
%0 Journal Article
%A Dong, Changchang
%A Meng, Jixiang
%A Liu, Juan
%T Dominated pair degree sum conditions of supereulerian digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 879-891
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a3/
%G en
%F DMGT_2024_44_3_a3
Dong, Changchang; Meng, Jixiang; Liu, Juan. Dominated pair degree sum conditions of supereulerian digraphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 879-891. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a3/

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Ed. (Springer, London, 2009). https://doi.org/10.1007/978-1-84800-998-1

[2] J. Bang-Jensen and A. Maddaloni, Sufficient conditions for a digraph to be supereulerian, J. Graph Theory 79 (2015) 8–20. https://doi.org/10.1002/jgt.21810

[3] F.T. Boesch, C. Suffel and R. Tindell, The spanning subgraphs of eulerian graphs, J. Graph Theory 1 (1977) 79–84. https://doi.org/10.1002/jgt.3190010115

[4] P.A. Catlin, Supereulerian graphs: A survey, J. Graph Theory 16 (1992) 177–196. https://doi.org/10.1002/jgt.3190160209

[5] Z.H. Chen and H.-J. Lai, Reduction techniques for supereulerian graphs and related topics–-a survey, in: Combinatorics and Graph Theory 95, vol.1, K. Tung-Hsin (Ed(s)), (World Sci. Publishing, River Edge 1995) 53–69.

[6] C. Dong, J. Meng and J. Liu, Sufficient Ore type condition for a digraph to be supereulerian, Appl. Math. Comput. 410 (2021) #126470. https://doi.org/10.1016/j.amc.2021.126470

[7] Y. Hong, H.-J. Lai and Q. Liu, Supereulerian digraphs, Discrete Math. 330 (2014) 87–95. https://doi.org/10.1016/j.disc.2014.04.018

[8] Y. Hong, Q. Liu and H.-J. Lai, Ore-type degree condition of supereulerian digraphs, Discrete Math. 339 (2016) 2042–2050. https://doi.org/10.1016/j.disc.2016.03.015

[9] H.-J. Lai, Y. Shao and H. Yan, An update on supereulerian graphs, WSEAS Trans. Math. 12 (2013) 926–940.

[10] W.R. Pulleyblank, A note on graphs spanned by Eulerian graphs, J. Graph Theory 3 (1979) 309–310. https://doi.org/10.1002/jgt.3190030316