## Resumen

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 (K^{n} (G)) | tends to infinity with n, where K^{n + 1} (G) is defined by K^{n + 1} (G) = K (K^{n} (G)) for n ≥ 1. In particular, our constructions show that for any k ≥ 2, the complement of the Cartesian product C^{k}, where C is the cycle of length 2 k + 1, is K-divergent.

Idioma original | Inglés |
---|---|

Páginas (desde-hasta) | 1125-1131 |

Número de páginas | 7 |

Publicación | Discrete Applied Mathematics |

Volumen | 156 |

N.º | 7 |

DOI | |

Estado | Publicada - 1 abr 2008 |

## Áreas temáticas de ASJC Scopus

- Matemáticas discretas y combinatorias
- Matemáticas aplicadas