zbMATH — the first resource for mathematics

Clique graphs of packed graphs. (English) Zbl 0603.05043
Let \(| G|\) be the number of vertices of a graph G and \(\omega\) (G) the number of vertices in the largest clique of G. The clique graph K(G) is the intersection graph of the cliques of G. For all G, \(| K(G)| \leq 2^{| G| -\omega (G)}\) [see B. Hedman, Discrete Math. 54, 161-166 (1986; Zbl 0569.05029)] and G is called packed if this is an equality. This paper corrects the characterization of the clique graphs of packed graphs given by Hedman.
Reviewer: C.R.J.Clapham

05C99 Graph theory
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Behzad, M; Chatrand, G; Lesniak-Foster, L, Graphs and digraphs, (1979), Prindle, Weber and Schmidt Boston
[2] Escalante, F; Toft, B, On clique-critical graphs, J. combin. theory ser. B, 17, 170-182, (1974) · Zbl 0288.05126
[3] Hedman, B, The maximum number of cliques in dense graphs, Discrete math., 54, 161-166, (1985) · Zbl 0569.05029
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.