Clique irreducibility of some iterative classes of graphs

Aparna Lakshmanan S.; A. Vijayakumar

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 2, page 307-321
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Aparna Lakshmanan S., and A. Vijayakumar. "Clique irreducibility of some iterative classes of graphs." Discussiones Mathematicae Graph Theory 28.2 (2008): 307-321. <http://eudml.org/doc/270328>.

@article{AparnaLakshmananS2008,
abstract = {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.},
author = {Aparna Lakshmanan S., A. Vijayakumar},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {line graphs; Gallai graphs; anti-Gallai graphs; clique irreducible graphs; clique vertex irreducible graphs},
language = {eng},
number = {2},
pages = {307-321},
title = {Clique irreducibility of some iterative classes of graphs},
url = {http://eudml.org/doc/270328},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Aparna Lakshmanan S.
AU - A. Vijayakumar
TI - Clique irreducibility of some iterative classes of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 2
SP - 307
EP - 321
AB - 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.
LA - eng
KW - line graphs; Gallai graphs; anti-Gallai graphs; clique irreducible graphs; clique vertex irreducible graphs
UR - http://eudml.org/doc/270328
ER -

References

top
  1. [1] Aparna Lakshmanan S., S.B. Rao and A. Vijayakumar, Gallai and anti-Gallai graphs of a graph, Math. Bohem. 132 (2007) 43-54. Zbl1174.05116
  2. [2] R. Balakrishnan and K. Ranganathan, A Text Book of Graph Theory (Springer, 1999). 
  3. [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. 
  4. [4] V.B. Le, Gallai graphs and anti-Gallai graphs, Discrete Math. 159 (1996) 179-189, doi: 10.1016/0012-365X(95)00109-A. Zbl0864.05031
  5. [5] E. Prisner, Graph Dynamics (Longman, 1995). 
  6. [6] E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220. Zbl0794.05113
  7. [7] W.D. Wallis and G.H. Zhang, On maximal clique irreducible graphs, J. Combin. Math. Combin. Comput. 8 (1990) 187-193. Zbl0735.05052

NotesEmbed ?

top

You must be logged in to post comments.