Back to Search
Start Over
Hamiltonian numbers in oriented graphs.
- Source :
- Journal of Combinatorial Optimization; Nov2017, Vol. 34 Issue 4, p1210-1217, 8p
- Publication Year :
- 2017
-
Abstract
- A hamiltonian walk of a digraph is a closed spanning directed walk with minimum length in the digraph. The length of a hamiltonian walk in a digraph D is called the hamiltonian number of D, denoted by h( D). In Chang and Tong (J Comb Optim 25:694-701, 2013), Chang and Tong proved that for a strongly connected digraph D of order n, $$n\le h(D)\le \lfloor \frac{(n+1)^2}{4} \rfloor $$ , and characterized the strongly connected digraphs of order n with hamiltonian number $$\lfloor \frac{(n+1)^2}{4} \rfloor $$ . In the paper, we characterized the strongly connected digraphs of order n with hamiltonian number $$\lfloor \frac{(n+1)^2}{4} \rfloor -1$$ and show that for any triple of integers n, k and t with $$n\ge 5$$ , $$n\ge k\ge 3$$ and $$t\ge 0$$ , there is a class of nonisomorphic digraphs with order n and hamiltonian number $$n(n-k+1)-t$$ . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13826905
- Volume :
- 34
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Journal of Combinatorial Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 125581256
- Full Text :
- https://doi.org/10.1007/s10878-017-0141-1