Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ².

If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given.

Authors and Affiliations

1.  CEREGMIA, Universite des Antilles et de la Guyane, BP 7209-97275 Schoelcher Cedex, Martinique, F W I, France. e-mail: a.ainouche@martinique.univ-ag.fr, , , , , , FR

   Ahmed Ainouche

2.  LRI, URA 410 CNRS, Bat 490, Universite de Paris-Sud, 91405 Orsay Cedex, France e-mail: km@lri.lri.fr, , , , , , FR

   Mekkia Kouider

Received: January 22, 1997 Final version received: February 15, 2000

Reprints and permissions