×

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

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
PDF BibTeX XML Cite
Full Text: DOI Link