- Tytuł:
- Variations on a sufficient condition for Hamiltonian graphs
- Autorzy:
-
Ainouche, Ahmed
Lapiquonne, Serge - Powiązania:
- https://bibliotekanauki.pl/articles/743758.pdf
- Data publikacji:
- 2007
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
cycles
partially square graph
degree sum
independent sets
neighborhood unions and intersections
dual closure - Opis:
-
Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ {x}$. In particular, this condition is satisfied if x does not center a claw (an induced $K_{1,3}$). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = {x,y,z} we define
σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|.
Flandrin et al. proved that a 2-connected graph G is hamiltonian if [σ̅]₃(X) ≥ n holds for any independent triple X in G. Replacing X in G by X in the larger graph G*, Wu et al. improved recently this result. In this paper we characterize the nonhamiltonian 2-connected graphs G satisfying the condition [σ̅]₃(X) ≥ n-1 where X is independent in G*. Using the concept of dual closure we (i) give a short proof of the above results and (ii) we show that each graph G satisfying this condition is hamiltonian if and only if its dual closure does not belong to two well defined exceptional classes of graphs. This implies that it takes a polynomial time to check the nonhamiltonicity or the hamiltonicity of such G. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 229-240
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł