- Tytuł:
- Extension of several sufficient conditions for Hamiltonian graphs
- Autorzy:
- Ainouche, Ahmed
- Powiązania:
- https://bibliotekanauki.pl/articles/744192.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
hamiltonian graph
dual closure
neighborhood closure - Opis:
-
Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖{u})|+d(u) ≥ n-1. Using the concept of dual closure, we prove that
1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇
2. G is nonhamiltonian if and only if its 0-dual closure is either the graph $(K_r ∪ Kₛ ∪ Kₜ) ∨ K₂$, 1 ≤ r ≤ s ≤ t or the graph $((n+1)/2)K₁ ∨ K_{(n-1)/2}$.
It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph satisfying the above condition. From this main result we derive a large number of extensions of previous sufficient conditions for hamiltonian graphs. All these results are sharp. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 23-39
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł