Vol. 11 No. 4 (2012): Mapana Journal of Sciences
Research Articles

Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs

  • R Mary Jeya Jothi,
  • A Amutha
R Mary Jeya Jothi
Research Scholar, Department of Mathematics, Sathyabama University, Chennai, Tamil Nadu.
A Amutha
Assistant Professor, Department of Mathematics, Sathyabama University, Chennai, Tamil Nadu.
DOI: https://doi.org/10.12723/mjs.23.10

Published 2012-09-25

Keywords

  • Super strongly perfect graph,
  • minimal dominating set,
  • domination and co-domination numbers and chordal graphs.

Abstract

A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. In this paper, we have investigated the characterization of Super Strongly Perfect graphs using odd cycles. We have given the characterization of Super Strongly Perfect graphs in chordal and strongly chordal graphs. We have presented the results of Chordal graphs in terms of domination and co - domination numbers γ and . We have given the relationship between diameter, domination and co - domination numbers of chordal graphs. Also we have analysed the structure of Super Strongly Perfect Graph in Chordal graphs and Strongly Chordal graphs.

References

  1. A Amutha, “Tree spanners of symmetric interconnection networks”, Ph.D. thesis, University of Madras, October 2006.
  2. A Amutha and R M J Jothi, Characterization of super strongly perfect graphs in bipartite graphs, Proceedings of an International Conference on Mathematical Modelling and Scientific Computation, vol. 1, pp. 183-185, 2012.
  3. J A Bondy and U S R Murty, Graph Theory with Applications, Elsevier Science, North Holland, 1976.
  4. A Brandstadt, V B Le and J P Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.
  5. Diestel and Reinhard, Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, vol. 173, pp. 6-9, 2005.
  6. G A Dirac, On Rigid Circuit Graphs, Abh. Math. Sem. Univ. Hamburg, Springer-Verlag, vol. 25, pp. 71-76, 1961.
  7. M Farber, Characterization of strongly chordal graphs, Discrete Mathematics, vol. 43, pp. 173-189, 1983.
  8. P C Fishburn, Utility Theory and Decision Making, Wiley, New York, 1970.
  9. F Gavril, The intersection graphs of subtrees are exactly the chordal graphs, Journal of Combinatorics Theory B, vol. 16, pp. 47-56, 1974.
  10. A Gibbons, Algorithmic Graph Theory, Cambridge University Press Publications, 1985.
  11. M C Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
  12. J Enright and G Kondrak, The application of chordal graphs to inferring phylogenetic trees of languages”, Proceedings of the 5th International Joint Conference on Natural Language Processing, pp. 545-552, Chiang Mai, Thailand, November 8 - 13, 2011.