Abstract | ||
---|---|---|
An affine graph is a pair (G,@s) where G is a graph and @s 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,@s) in terms of the orbits of @s. 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 2k+1, is K-divergent. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.dam.2007.05.050 | Discrete Applied Mathematics |
Keywords | Field | DocType |
clique operator,expansivity,cartesian product,cliques k,new family,affine graphs,expansive graph,affine graph,k-divergent graph,stronger notion,graph g,certain colorings,new example,intersection graph | Discrete mathematics,Strongly regular graph,Combinatorics,Line graph,Edge-transitive graph,Vertex-transitive graph,Bound graph,Graph power,Symmetric graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
156 | 7 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.42 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martín Matamala | 1 | 158 | 21.63 |
José Zamora | 2 | 7 | 5.95 |