کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419238 683758 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On self-clique shoal graphs
ترجمه فارسی عنوان
درباره نمودارهای خوددسته shoal
کلمات کلیدی
نمودارهای دسته؛ نمودارهای خوددسته؛ پیوند ثابت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The clique graph   of a graph GG is the intersection graph K(G)K(G) of its (maximal) cliques, and GG is self-clique   if K(G)K(G) is isomorphic to  GG. A graph GG is locally  HH if the neighborhood of each vertex is isomorphic to  HH. Assuming that each clique of the regular and self-clique graph  GG is a triangle, it is known that GG can only be rr-regular for r∈{4,5,6}r∈{4,5,6} and GG must be, depending on rr, a locally HH graph for some H∈{P4,P2∪P3,3P2}H∈{P4,P2∪P3,3P2}. The self-clique locally P4P4 graphs are easy to classify, but only a family of locally  HH self-clique graphs was known for H=P2∪P3H=P2∪P3, and another one for H=3P2H=3P2.We study locally P2∪P3P2∪P3 graphs (i.e.  shoal graphs  ). We show that all previously known shoal graphs were self-clique. We give a bijection from (finite) shoal graphs to 2-regular digraphs without directed 3-cycles. Under this translation, self-clique graphs correspond to self-dual digraphs, which simplifies constructions, calculations and proofs. We compute the numbers, for each n≤28n≤28, of self-clique and non-self-clique shoal graphs of order nn, and also prove that these numbers grow at least exponentially with  nn.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 86–100
نویسندگان
, , ,