Article in press
Authors:
Title:
Antidirected spanning trail of digraphs with $\alpha_{2}$-stable number 3
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-12-13 , Revised: 2024-08-16 , Accepted: 2024-08-16 , Available online: 2024-09-13 , https://doi.org/10.7151/dmgt.2560
Abstract:
Let $D$ be a digraph with vertex set $V(D)$ and arc set $A(D)$. An antidirected
spanning trail of $D$ is a spanning trail in which consecutive arcs have
opposite directions and each arc of $D$ occurs at most once. Let
$\alpha_{2}(D) = \max\{|X|: X \subseteq V(D)$ and $D[X]$ has no 2-cycle$\}$ be
the $\alpha_{2}(D)$-stable number. When $\alpha_{2}(D)=2$, we have demonstrated
that every weakly connected digraph $D$ with $\alpha_{2}(D)=2$ has an
antidirected Hamiltonian path, and have provided a necessary and sufficient
condition for strongly connected digraph $D$ with $\alpha_{2}(D)=2$ to have an
antidirected Hamiltonian cycle.
In this paper, we first determine two families $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$ of well-characterized strongly connected digraphs with
$\alpha_{2}$-stable number 3 such that, for any strongly connected digraph
$D\in \mathcal{D}_{1}\cup \mathcal{D}_{2}$, $D$ does not have an antidirected
spanning trail. And, we further prove that every strongly connected digraph $D$
with $\alpha_{2}(D)=3$ has an antidirected spanning trail if and only if
$D\not\in \mathcal{D}_{1}\cup \mathcal{D}_{2}$.
Keywords:
$\alpha_{2}$-stable set, antidirected spanning trail, complete graph, digraph
References:
- J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Edition (Springer, London, 2009).
https://doi.org/10.1007/978-1-84800-998-1 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - A.H. Busch, M.S. Jacobson, T. Morris, M.J. Plantholt and S.K. Tipnis, Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs, Graphs Combin. 29 (2013) 359–364.
https://doi.org/10.1007/s00373-011-1116-0 - M.C. Cai, A counterexample to a conjecture of grant, Discrete Math. 44 (1983) 111.
https://doi.org/10.1016/0012-365X(83)90010-9 - N. Chakroun and D. Sotteau, Chvátal-Erdős theorem for digraphs, Cycles and Rays, G. Hahn, G. Sabidussi and R.E. Woodrow (Ed(s)), NATO ASI Series 301, (Springer, Dordrecht, 1990) 75–86.
https://doi.org/10.1007/978-94-009-0517-7\_7 - B. Chen, S. Gerke, G. Gutin, H. Lei, H. Parker-Cox and Y.C. Zhou, On the $k$-anti-traceability Conjecture (2024).
arXiv: 2403.19312 - V. Chvátal and P. Erdős, A note on Hamiltonian circuits, Discrete Math. 2 (1972) 111–113.
https://doi.org/10.1016/0012-365X(72)90079-9 - B. Grünbaum, Antidirected Hamiltonian paths in tournaments, J. Combin. Theory Ser. B 11 (1971) 249–257.
https://doi.org/10.1016/0095-8956(71)90035-9 - P. Hell and M. Rosenfeld, Antidirected Hamiltonian paths between specified vertices of a tournament, Discrete Appl. Math. 117 (2002) 87–98.
https://doi.org/10.1016/S0166-218X(01)00197-4 - B. Jackson and O. Ordaz, Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey, Discrete Math. 84 (1990) 241–254.
https://doi.org/10.1016/0012-365X(90)90130-A - V. Petrović, Antidirected Hamiltonian circuits in tournaments, in: Proc. 4th Yugoslav Seminar on Graph Theory, Novi Sad (1983) 259–269.
- M.J. Plantholt and S.K. Tipnis, Vertex-oriented Hamilton cycles in directed graphs, Electron. J. Combin. 16(1) (2009) #R115.
https://doi.org/10.37236/204 - M. Rosenfeld, Antidirected Hamiltonian paths in tournaments, J. Combin. Theory Ser. B 12 (1972) 93–99.
https://doi.org/10.1016/0095-8956(72)90035-4 - M. Rosenfeld, Antidirected Hamiltonian circuits in tournaments, J. Combin. Theory Ser. B 16 (1974) 234–242.
https://doi.org/10.1016/0095-8956(74)90069-0 - C. Thomassen, Antidirected Hamilton circuits and paths in tournaments, Math. Ann. 201 (1973) 231–238.
https://doi.org/10.1007/BF01427945 - H. Yang, J. Liu and J.X. Meng, Antidirected Hamiltonian paths and cycles of digraphs with $\alpha_{2}$-stable number $2$, Graphs Combin. 39 (2023) 73.
https://doi.org/10.1007/s00373-023-02667-3
Close