کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420618 683961 2008 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new family of expansive graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A new family of expansive graphs
چکیده انگلیسی

An affine graph   is a pair (G,σ)(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,σ)(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)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))||V(Kn(G))| tends to infinity with n  , where Kn+1(G)Kn+1(G) is defined by Kn+1(G)=K(Kn(G))Kn+1(G)=K(Kn(G)) for n⩾1n⩾1. In particular, our constructions show that for any k⩾2k⩾2, the complement of the Cartesian product CkCk, where C   is the cycle of length 2k+12k+1, is KK-divergent.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 7, 1 April 2008, Pages 1125–1131
نویسندگان
, ,