Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419238 | Discrete Applied Mathematics | 2016 | 15 Pages |
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.