On self-clique graphs with given clique sizes
type: Item
instance of: scholarly article
title: On self-clique graphs with given clique sizes
zbMATH Open document ID: 0945.05050
DOI: 10.1016/S0012-365X(99)00286-1
author: Gek L. Chia
published in: Discrete Mathematics
publication date: 2000-10-08T00:00:00Z
review text: Let \(G\) be a finite simple graph and let the set of all its cliques be denoted by \({\mathfrak K}(G)\). The clique graph \(K(G)\) of \(G\) is the graph whose vertex set is \({\mathfrak K}(G)\) and two vertices are adjacent in \(K(G)\) iff the corresponding cliques have non-empty intersection; \(G\) is said to be self-clique if it is isomorphic to \(K(G)\). As a consequence of a theorem of Harary the following Theorem 1 is given: If \(G\) is a connected graph whose cliques are all of size 2, then \(G\) is self-clique iff \(G\) is a cycle of length at least 4. A given finite sequence of positive integers \((a_1,a_2,\dots, a_m)\) is called clique size sequence of a graph \(G\) if the \(m\) elements in \({\mathfrak K}(G)\) can be arranged in such a way that the \(i\)th element of \({\mathfrak K}(G)\) is of size \(a_i\), \(i= 1,2,\dots, m\). The result of the present paper is the characterization of all connected self-clique graphs with the clique size sequence \((2,\dots, 2,n)\) where \(n\geq 3\). For this purpose the author constructs two families \({\mathfrak G}_{r,s}\) and \({\mathfrak H}_{t,q}\) of graphs of the clique size sequence mentioned above with integers \(r\geq 0\), \(s\geq 1\), \(t\geq 0\), \(q\geq 0\) such that \(2r+ s= n\), \(2t+ q= n-1\), respectively, by applying certain graph-theoretical operations on a complete graph \(K_n\) on \(n\) vertices. This is also demonstrated by six figures. By an extensive proof the author gets the following result (Theorem 2): Let \(G\) be a connected graph whose clique size sequence is \((2,\dots, 2,n)\), \(n\geq 3\). Then \(G\) is self-clique iff \(G\in{\mathfrak G}_{r,s}\cup{\mathfrak H}_{t,q}\).
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1421655
zbMATH Keywords: clique graph
zbMATH Keywords: self-clique
zbMATH Keywords: clique size sequence
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00286-1
OpenAlex ID: W2133128623
description: scientific article; zbMATH DE number 1421655