ir-Excellent Graphs


  • I. Kulrekha Mudartha
  • R. Sundareswaran
  • V. Swaminathan


Terasa W. Haynes et. al. [7], introduced the concept of irredun-
dance in graphs. A subset S of V (G) is called an irredundant set of G if for every vertex u 2 S, pn[u; S] ̸= ϕ. The minimum (maximum)cardinality of a maximal irredundant set of G is called the irredundance number of G (upper irredundance number of G) and is denoted by ir(G)(IR(G)). A subset V (G) is called an ir-set if it is an irredundant set of G of cardinality ir(G). A vertex u 2 V (G) is called ir-good if u belongs to an ir-set of G. G is said to be ir-
excellent if every vertex of G is ir-good. In this paper, a study of the excellent graphs with respect to irredundance is initiated.


[1] J. A. Bondy and U. S. R Murthy. Graph theory with applications. Macmillan press, 1976.

[2] G. H. Fricke, T. W. Haynes and S. T. Hetniemi, S. M. Hedetniemi and R. C. Laskar. Excellent trees. Bull. Inst. Combin. Appl., 34(2002), 27-38.

[3] R. Laskar and K. Peters. Domination and irredundance in graph. Technical Report 434, Dept. Mathematical Sciences, Clemson Univ., 1983.

[4] N. Sridharan and M. Yamuna. Excellent-Just Excellent-Very Excellent Graphs. Journal of Math. Phy. Sci., 14(5)(1980), 471-475.

[5] N. Sridharan and M. Yamuna. A Note on Excellent Graphs. Ars Combinatoria, 78(2006), 267-276.

[6] N. Sridharan and M. Yamuna. Excellent-Just - Excellent-Very Excellent Graphs. Ph.D Thesis, Alagappa University, 2003.

[7] T. W. Haynes, S. T. Hedetneimi and P. J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker Inc. 1998.

[8] T. W. Haynes and M. A. Henning. A characterization of i-excellent trees. Discrete Math., 248(1-3)(2002), 69-77.