Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: partially square graph

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Remarks on partially square graphs, hamiltonicity and circumference

100%

Kheddouci H.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 2

255-266

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and 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 the case where G is a claw-free graph, G* is equal to G². We define $σ°ₜ = min{ ∑_{x∈S} d_G(x):S is an independent set in G* and |S| = t}$. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Variations on a sufficient condition for Hamiltonian graphs

75%

Ainouche A., Lapiquonne S.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 2

229-240

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Ainouche A.

1 Kheddouci H.

1 Lapiquonne S.

1 2007

1 2001

Wyniki wyszukiwania

Remarks on partially square graphs, hamiltonicity and circumference

Variations on a sufficient condition for Hamiltonian graphs