A new family of expansive graphs

Matamala M.; Zamora J.

Abstract

An affine graph is a pair (G, σ) where G is a graph and σ is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G, σ) in terms of the orbits of σ. On the other hand, we establish a relation between certain colorings of a graph G and the intersection graph of its cliques K (G). By using the results we construct new examples of expansive graphs. The expansive graphs were introduced by Neumann-Lara in 1981 as a stronger notion of the K-divergent graphs. A graph G is K-divergent if the sequence | V (Kn (G)) | tends to infinity with n, where Kn + 1 (G) is defined by Kn + 1 (G) = K (Kn (G)) for n ≥ 1. In particular, our constructions show that for any k ≥ 2, the complement of the Cartesian product Ck, where C is the cycle of length 2 k + 1, is K-divergent. © 2007 Elsevier B.V. All rights reserved.

Más información

Título según WOS: A new family of expansive graphs
Título según SCOPUS: A new family of expansive graphs
Título de la Revista: DISCRETE APPLIED MATHEMATICS
Volumen: 156
Número: 7
Editorial: Elsevier
Fecha de publicación: 2008
Página de inicio: 1125
Página final: 1131
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0166218X07002946
DOI:

10.1016/j.dam.2007.05.050

Notas: ISI, SCOPUS