# zbMATH — the first resource for mathematics

On self-clique shoal graphs. (English) Zbl 1333.05226
Summary: The clique graph of a graph $$G$$ is the intersection graph $$K(G)$$ of its (maximal) cliques, and $$G$$ is self-clique if $$K(G)$$ is isomorphic to $$G$$. A graph $$G$$ is locally $$H$$ if the neighborhood of each vertex is isomorphic to $$H$$. Assuming that each clique of the regular and self-clique graph $$G$$ is a triangle, it is known that $$G$$ can only be $$r$$-regular for $$r \in \{4, 5, 6 \}$$ and $$G$$ must be, depending on $$r$$, a locally $$H$$ graph for some $$H \in \{P_4, P_2 \cup P_3, 3 P_2 \}$$. The self-clique locally $$P_4$$ graphs are easy to classify, but only a family of locally $$H$$ self-clique graphs was known for $$H = P_2 \cup P_3$$, and another one for $$H = 3 P_2$$.
We study locally $$P_2 \cup P_3$$ 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 \leq 28$$, of self-clique and non-self-clique shoal graphs of order $$n$$, and also prove that these numbers grow at least exponentially with $$n$$.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
##### Keywords:
clique graphs; self-clique graphs; constant link
##### Software:
GAP; GENREG; nauty; OEIS
Full Text:
##### References:
  Balakrishnan, R.; Paulraja, P., Self-clique graphs and diameters of iterated clique graphs, Util. Math., 29, 263-268, (1986) · Zbl 0614.05053  Bondy, A.; Durán, G.; Lin, M. C.; Szwarcfiter, J. L., A sufficient condition for self-clique graphs, Electron. Notes Discrete Math., 7, 19-23, (2001)  Bondy, A.; Durán, G.; Lin, M. C.; Szwarcfiter, J. L., Self-clique graphs and matrix permutations, J. Graph Theory, 44, 178-192, (2003) · Zbl 1031.05115  Bonomo, F., Self-clique Helly circular-arc graphs, Discrete Math., 306, 595-597, (2006) · Zbl 1087.05042  Chia, G. L., On self-clique graphs with given clique sizes, Discrete Math., 212, 185-189, (2000), Combinatorics and applications (Tianjin, 1996) · Zbl 0945.05050  Chia, G. L.; Ong, P. H., On self-clique graphs with given clique sizes. II, Discrete Math., 309, 1538-1547, (2009) · Zbl 1194.05131  Chia, G. L.; Ong, P. H., On self-clique graphs all of whose cliques have equal size, Ars Combin., 105, 435-449, (2012) · Zbl 1274.05350  Dragan, F. F., Centers of graphs and the Helly property, (1989), Moldava State University Chisinaˇu, Moldava, (in Russian)  Escalante, F., Über iterierte clique-graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68, (1973) · Zbl 0266.05116  The GAP Group. GAP—Groups, Algorithms, and Programming, Version 4.3, 2002. http://www.gap-system.org.  Hall, J. I., Graphs with constant link and small degree or order, J. Graph Theory, 9, 419-444, (1985) · Zbl 0582.05049  Larrión, F.; Neumann-Lara, V., Locally $$C_6$$ graphs are clique divergent, Discrete Math., 215, 159-170, (2000) · Zbl 0961.05056  Larrión, F.; Neumann-Lara, V.; Pizaña, M. A.; Porter, T. D., Self clique graphs with prescribed clique-sizes, Congr. Numer., 157, 173-182, (2002) · Zbl 1032.05101  Larrión, F.; Neumann-Lara, V.; Pizaña, M. A.; Porter, T. D., Recognizing self-clique graphs, Mat. Contemp., 25, 125-133, (2003) · Zbl 1049.05057  Larrión, F.; Neumann-Lara, V.; Pizaña, M. A.; Porter, T. D., A hierarchy of self-clique graphs, Discrete Math., 282, 193-208, (2004) · Zbl 1042.05073  Larrión, F.; Pizaña, M. A., On hereditary clique-Helly self-clique graphs, Discrete Appl. Math., 156, 1157-1167, (2008) · Zbl 1138.05054  B.D. McKay, nauty user’s guide (version 2.4). Technical Report TR-CS-90-02, Australian National University, Computer Science Department, 1990, http://cs.anu.edu.au/ bdm/nauty/.  Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146, (1999) · Zbl 0918.05062  Oeis: The on-line encyclopedia of integer sequences. http://oeis.org/A006820.  Read, R. C.; Wilson, R. J., An atlas of graphs, (1998), Oxford Science Publications. The Clarendon Press Oxford University Press New York · Zbl 0908.05001  Sabidussi, G., Graph derivatives, Math. Z., 76, 385-401, (1961) · Zbl 0109.16404  Spanier, E. H., Algebraic topology, (1981), Springer-Verlag New York, Corrected reprint  Stillwell, J., Geometry of surfaces, (1992), Universitext, Springer-Verlag New York · Zbl 0752.53002  Szwarcfiter, J. L., Recognizing clique-Helly graphs, Ars Combin., 45, 29-32, (1997) · Zbl 0933.05127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.