Article ID Journal Published Year Pages File Type
419238 Discrete Applied Mathematics 2016 15 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,