On clique-complete graphs
type: Item
instance of: scholarly article
title: On clique-complete graphs
zbMATH Open document ID: 0894.05045
DOI: 10.1016/S0012-365X(97)00085-X
author: Cláudio L. Lucchesi
author: Célia P. de Mello
author: Jayme L. Szwarcfiter
published in: Discrete Mathematics
publication date: 1998-09-07T00:00:00Z
review text: Let \(G\) be a simple graph. The clique graph \(K(G)\) is the intersection graph of the maximal cliques of \(G\). A vertex in \(G\) is universal if it is adjacent to all other vertices in \(G\). The \(n\)th iterated clique graph of \(G\) is defined by \(K^{(n)}= K(K^{n-1} (G))\) and \(G\) is \(n\)-convergent if \(K^n (G)\) is isomorphic to the one-vertex graph \(K_1\). \(G\) is called clique-complete if \(K^2(G)\simeq K_1\), i.e. a graph is clique-complete iff every two of its maximal cliques intersect. \(G\) is said to be critical if for each induced proper subgraph \(H\) of \(G\), either \(H\) contains an universal vertex, or \(H\) is not clique-complete. Finally a graph \(Q_n= (V,E)\), \(n\geq 3\), is defined in following manner: (1) \(V(Q_n)= \{u_1, u_2,\dots, u_n\}\cup \{v_1, v_2,\dots, v_n\}\); (2) the subgraph of \(Q_n\) induced by \(\{v_1,\dots, v_n\}\) is isomorphic to the complement \(\overline{C}_n\) of the circuit \(C_n\); and (3) for each \(i\) with \(1\leq i\leq n\) holds \(N[u_i]= V(Q_n)- v_i\) for the neighborhood \(N[u_i]\) of \(u_i\). (The figures of the graphs \(\overline{Q}_3\) \(\overline{Q}_5\) are given in the paper.) The main result (Theorem 2) consists in a description of the family of minimal graphs which are clique-complete but have no universal vertices: A graph free of universal vertices is clique-complete and critical iff it is isomorphic to \(Q_{2n+1}\), for some positive integer \(n\). Moreover the authors show that the problem of recognizing clique-complete graphs is Co-NP-complete (Theorem 1). Also they give four additional conclusions, for example, that every clique-complete interval graph contains a universal vertex (Corollary 15).
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1130778
zbMATH Keywords: critical graph
zbMATH Keywords: clique graph
zbMATH Keywords: clique-complete
zbMATH Keywords: universal vertices
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Clique graphs and Helly graphs
cites work: On clique convergent graphs
cites work: Über iterierte Clique-Graphen
cites work: A partial characterization of clique graphs
cites work: Clique graphs of time graphs
cites work: Q3328583
cites work: Q4288086
cites work: Convergence of iterated clique graphs
cites work: Q4940014
cites work: Q3980562
full work available at URL: s0012-365x(97)00085-x
OpenAlex ID: W1981103638
description: scientific article; zbMATH DE number 1130778