Article in volume
Authors:
Title:
Dominated pair degree sum conditions of supereulerian digraphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 879-891
Received: 2021-11-11 , Revised: 2022-09-27 , Accepted: 2022-10-01 , Available online: 2022-11-14 , https://doi.org/10.7151/dmgt.2476
Abstract:
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\leq t\leq n-3$ so that any strong digraph with $n$ vertices satisfying either
both $d(u) \geq n -1+ t$ and $d(v) \geq n-2- t$ or both $d(u) \geq n-2- t$ and
$d(v) \geq 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)\}\geq 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
References:
- 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 - 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 - 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 - P.A. Catlin, Supereulerian graphs: A survey, J. Graph Theory 16 (1992) 177–196.
https://doi.org/10.1002/jgt.3190160209 - 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.
- 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 - 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 - 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 - H.-J. Lai, Y. Shao and H. Yan, An update on supereulerian graphs, WSEAS Trans. Math. 12 (2013) 926–940.
- 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
Close