Hamiltonism and Partially Square Graphs |
| |
Authors: | Ahmed Ainouche Mekkia Kouider |
| |
Institution: | (1) Ceregmia, Université des Antilles et de la Guyane, BP 7209-97275 Schoelcher Cedex, Martinique. FWI. e-mail: a.ainouche@martinique.univ-ag.fr, MQ;(2) LRI, URA 410 CNRS, Bat 490, Université de Paris-Sud, 91405 Orsay Cedex, France. e-mail: km@lri.lri.fr, FR |
| |
Abstract: | Given a graph G, we define its partially square graph G
* as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N
Gx]⊆N
Gu]∪N
G v], where N
Gx]=N
G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K
1,3). Obviously G⊆G
*⊆G
2, where G
2 is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G
*) of G
* does not exceed k. If we replace G
* by G we get a well known result of Chvátal and Erdo?s. If G is claw-free and G
* is replaced by G
2 then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G
* for other hamiltonian properties are also given in this paper.
Received: June 17, 1996 Revised: October 30, 1998 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|