## 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
Full Text: