Back to Search
Start Over
Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs.
- Source :
-
Discrete Mathematics & Theoretical Computer Science (DMTCS) . 2021, Vol. 23 Issue 3, p1-12. 12p. - Publication Year :
- 2021
-
Abstract
- Let D be a strong balanced digraph on 2a vertices. Adamus et al. have proved that D is hamiltonian if d(u)+d(v) ≥ 3a whenever uv ∈ A(D) and vu ∈ A(D). The lower bound 3a is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if d(u) + d(v) ≥ 3a − 1 whenever uv ∈ A(D) and vu ∈ A(D), then D is traceable. The lower bound 3a − 1 is tight. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DIRECTED graphs
*ALGORITHMS
*FIBONACCI sequence
*NUMBER theory
*MACHINE theory
Subjects
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- 23
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics & Theoretical Computer Science (DMTCS)
- Publication Type :
- Academic Journal
- Accession number :
- 155291082