Spanning Directed Trails in Semicomplete 3-Multipartite Digraphs

Article Sidebar

PDF
Published: Mar 15, 2025
DOI: https://doi.org/10.26629/uzjns.2025.03
Keywords:
arcs-strong connectivity; stability number; spanning trail; supereulerian (closed spanning trails) digraphs; semicomplete 3-multipartite digraphs s.

Main Article Content

Omaema O Lasfar
University of Zawia.
https://orcid.org/0009-0007-1387-6780

Abstract

The study of spanning trails in digraphs associates two fundamental concepts: connectivity and independence. For general digraphs, establishing universal conditions remains an open challenge, but semi-complete multipartite digraphs reveal precise connectivity restrictions due to their well-defined structure. In this work, we prove that every strongly connected semi-complete 3-multipartite digraph D with arc-strong connectivity $\lambda(D) \ge \alpha(D)-1$ contains a spanning directed trail. This result provides evidence that multipartite structures may require weaker connectivity conditions than arbitrary digraphs, opening new directions for studying spanning trails in constrained digraph classes.

Article Details

How to Cite
[1]
O. O. Lasfar, “Spanning Directed Trails in Semicomplete 3-Multipartite Digraphs”, UZJNS, vol. 2, no. 1, pp. 17–19, month-03 2025.
Issue
Vol. 2 No. 1 (2025): Univ Zawia J Nat Sci
Section
Mathematics
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

References

J.A. Bondy and U.S.R. Murty, Graph Theory. Springer, New York, 2008.

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Edition. Springer- Verlag, London, 2009.

Y. Hong, H.-J. Lai and Q. Liu. ''Supereulerian Digraphs.'' Discrete Math 330 (2014): 87-95.

Y. Hong, Q. Liu and H.-J. Lai. ''Ore-type degree condition of supereulerian digraphs.'' Discrete Math 339 (2016): 2042-2050.

J. Bang-Jensen and A. Maddaloni, ''Sufficient conditions for a digraph to be supereulerian.'' Graph Theory 79 (1) (2015): 8-20.

J. Bang-Jensen, H. Déprés and A. Yeo. ''Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments.'' Discrete Math 343 (2020): 112-129.

J. Bang-Jensen, F. Havet and A. Yeo. ''Spanning eulerian subdigraphs in semicomplete digraphs.'' Graph Theory 100 (2) (2022): 294-314.

F. Liu, Z.-X. Tian and D. Li. ''Supereulerian Locally Semicomplete Multipartite Digraphs.'' International J. Math. Combin 2 (2017): 123-128.

V. Chvátal and P. Erdös. ''A note on Hamiltonian circuits. '' Discrete Math 2 (1972): 111-113.

C. Thomassen. ''Long cycles in digraphs.'' Proc. London Math. Soc 42 (1981): 231-251.