Clique irreducibility of some iterative classes of graphs. (English) Zbl 1156.05045

Lakshmanan S., Aparna; Vijaykumar, A.

Discuss. Math., Graph Theory 28, No. 2, 307-321 (2008).

Summary: Two notions, the clique irreducibility and clique vertex irreducibility are discussed. A graph \(G\) is clique irreducible if every clique in \(G\) of size at least two, has an edge which does not lie in any other clique of \(G\) and it is clique vertex irreducible if every clique in \(G\) has a vertex which does not lie in any other clique of \(G\). It is proved that \(L(G)\) is clique irreducible if and only if every triangle in \(G\) has a vertex of degree two. The conditions for the iterations of line graph, the Gallai graphs, the anti-Gallai graphs and its iterations to be clique irreducible and clique vertex irreducible are also obtained.

MSC:

05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35	Extremal problems in graph theory

Keywords:

line graphs; Gallai graphs; anti-Gallai graphs; clique irreducible graphs; clique vertex irreducible graphs