Clique irreducibility of some iterative classes of graphs
Aparna Lakshmanan S. ; A. Vijayakumar
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 307-321 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper, 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.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270328 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1407,
     author = {Aparna Lakshmanan S. and A. Vijayakumar},
     title = {Clique irreducibility of some iterative classes of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {307-321},
     zbl = {1156.05045},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1407}
}

Aparna Lakshmanan S.; A. Vijayakumar. Clique irreducibility of some iterative classes of graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 307-321. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1407/

[000] [1] Aparna Lakshmanan S., S.B. Rao and A. Vijayakumar, Gallai and anti-Gallai graphs of a graph, Math. Bohem. 132 (2007) 43-54. | Zbl 1174.05116

[001] [2] R. Balakrishnan and K. Ranganathan, A Text Book of Graph Theory (Springer, 1999).

[002] [3] L. Chong-Keang and P. Yee-Hock, On graphs without multicliqual edges, J. Graph Theory 5 (1981) 443-451, doi: 10.1002/jgt.3190050416.

[003] [4] V.B. Le, Gallai graphs and anti-Gallai graphs, Discrete Math. 159 (1996) 179-189, doi: 10.1016/0012-365X(95)00109-A. | Zbl 0864.05031

[004] [5] E. Prisner, Graph Dynamics (Longman, 1995).

[005] [6] E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220. | Zbl 0794.05113

[006] [7] W.D. Wallis and G.H. Zhang, On maximal clique irreducible graphs, J. Combin. Math. Combin. Comput. 8 (1990) 187-193. | Zbl 0735.05052