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\).

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI
[1] Balakrishnan, R.; Paulraja, P., Self-clique graphs and diameters of iterated clique graphs, Util. Math., 29, 263-268, (1986) · Zbl 0614.05053
[2] 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)
[3] 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
[4] Bonomo, F., Self-clique Helly circular-arc graphs, Discrete Math., 306, 595-597, (2006) · Zbl 1087.05042
[5] 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
[6] Chia, G. L.; Ong, P. H., On self-clique graphs with given clique sizes. II, Discrete Math., 309, 1538-1547, (2009) · Zbl 1194.05131
[7] 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
[8] Dragan, F. F., Centers of graphs and the Helly property, (1989), Moldava State University Chisinaˇu, Moldava, (in Russian)
[9] Escalante, F., Über iterierte clique-graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68, (1973) · Zbl 0266.05116
[10] The GAP Group. GAP—Groups, Algorithms, and Programming, Version 4.3, 2002. http://www.gap-system.org.
[11] Hall, J. I., Graphs with constant link and small degree or order, J. Graph Theory, 9, 419-444, (1985) · Zbl 0582.05049
[12] Larrión, F.; Neumann-Lara, V., Locally \(C_6\) graphs are clique divergent, Discrete Math., 215, 159-170, (2000) · Zbl 0961.05056
[13] 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
[14] 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
[15] 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
[16] Larrión, F.; Pizaña, M. A., On hereditary clique-Helly self-clique graphs, Discrete Appl. Math., 156, 1157-1167, (2008) · Zbl 1138.05054
[17] 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/.
[18] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146, (1999) · Zbl 0918.05062
[19] Oeis: The on-line encyclopedia of integer sequences. http://oeis.org/A006820.
[20] 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
[21] Sabidussi, G., Graph derivatives, Math. Z., 76, 385-401, (1961) · Zbl 0109.16404
[22] Spanier, E. H., Algebraic topology, (1981), Springer-Verlag New York, Corrected reprint
[23] Stillwell, J., Geometry of surfaces, (1992), Universitext, Springer-Verlag New York · Zbl 0752.53002
[24] 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.