A new family of expansive graphs |
| |
Authors: | Martín Matamala José Zamora |
| |
Institution: | a Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Casilla 170-3, Correo 3, Santiago, Chile b Centro de Modelamiento Matemático Universidad de Chileand UMR 2071-CNRS, Casilla 170-3, Correo 3, Santiago, Chile |
| |
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 2k+1, is K-divergent. |
| |
Keywords: | Clique operator Affine graphs Expansivity |
本文献已被 ScienceDirect 等数据库收录! |
|