Search

Let k ≥ 2 be an integer. We say that a graph G is (K 2 ∪ k K 1) -free if it does not contain K 2 ∪ k K 1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2 k -connected (K 2 ∪ k K 1) -free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k -connected (K 2 ∪ k K 1) -free graph with minimum degree at least 3 (k − 1) 2 is hamiltonian or the Petersen graph. [ABSTRACT FROM AUTHOR]

Cohen et al. conjectured that, for each oriented cycle C , there exists an integer f (C) such that any f (C) -chromatic strong digraph contains a subdivision of C as a subdigraph. In the same paper, Cohen et al. proved this conjecture for cycles with two blocks by showing that the chromatic number of strong digraphs that include no subdivision of a cycle with two blocks, with lengths of k 1 and k 2 , is bounded from above by O ((k 1 + k 2) 4). More recently, Kim et al. improved this upper bound to O ((k 1 + k 2) 2) for the class of strong digraphs and to O (k 1 + k 2) for the class of Hamiltonian digraphs. In this paper, we confirm Cohen et al.'s conjecture for Hamiltonian digraphs. We demonstrate a stronger version by showing that every 3 n -chromatic Hamiltonian digraph contains a subdivision for every oriented cycle of order n. [ABSTRACT FROM AUTHOR]

In 1996, Bang-Jensen, Gutin, and Li proposed the following conjecture: If D is a strong digraph of order n where n ≥ 2 with the property that d (x) + d (y) ≥ 2 n − 1 for every pair of dominated non-adjacent vertices { x , y } , then D is hamiltonian. In this paper, we give an infinite family of counterexamples to this conjecture. In the same paper, they showed that for the above x , y , if they satisfy the condition either d (x) ≥ n , d (y) ≥ n − 1 or d (x) ≥ n − 1 , d (y) ≥ n , then D is hamiltonian. It is natural to ask if there is an integer k ≥ 1 such that every strong digraph of order n satisfying either d (x) ≥ n + k , d (y) ≥ n − 1 − k , or d (x) ≥ n − 1 − k , d (y) ≥ n + k , for every pair of dominated non-adjacent vertices { x , y } , is hamiltonian. In this paper, we show that k must be at most n − 5 and prove that every strong digraph with k = n − 4 satisfying the above condition is hamiltonian, except for one digraph on 5 vertices. [ABSTRACT FROM AUTHOR]