On Sufficient Conditions for a Graph to be Hamiltonian
スポンサーリンク
概要
- 論文の詳細を見る
A graph G=(V, E) is called a complete semi-bigraph and denoted by K'(l, m) if the vertex set can be partitioned into two subsets V_1(|V_1|=l) and V_2(|V_2|=m) such that [u, v]∉E for every u, v∈V_1(u≠v), and [v_1, v_2]∈E for every v_1∈V_1 and v_2∈V_2. THEOREM. Let G=(V, E) be an undirected 2-connected graph with n≧3 vertices and satisfying the following: [u, v]∉E⇒d(u)+d(v)≧n-1. Then G is either hamiltonian or a complete semi-bigraph K'(n+1/2, n-1/2). In particular, if n is even, then G must be hamiltonian.
- お茶の水女子大学の論文