On clique-complete graphs

DOI10.1016/S0012-365X(97)00085-XMaRDI QIDQ1382831zbMATH OpenOpenAlexFDO

Authors Cláudio L. Lucchesi, Célia P. de Mello, Jayme L. Szwarcfiter

Publication date 7 September 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(97)00085-x

zbMATH Keywords

clique graph clique-complete critical graph universal vertices

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

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

Recommendations

Cites work

Cited in

(19)

This page was built for publication: On clique-complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382831)