Open Access Open Access  Restricted Access Subscription or Fee Access

Recognizing the Structure of Super Strongly Perfect Graphs Using Perfect Graphs and Strongly Perfect Graphs

R. Mary Jeya Jothi, A. Amutha

Abstract


A Graph G is Super Strongly Perfect Graph if every induced sub graphs H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. We have given results about two important family members of Perfect graphs (i.e.,) Strongly Perfect Graphs and Super Strongly Perfect Graphs. We have discussed the structure of Super Strongly Perfect Graphs for Perfect Graphs like, Bipartite Graphs and Trees. We have also discussed the Super Strongly Perfect Graphs on Planar Graphs, Digraphs and 2 - Connected Graphs. We have found the relation between Strongly Perfect Graphs and Super Strongly Perfect Graphs.

Keywords


Digraphs, Perfect Graphs, Planar Graphs, Strongly Perfect Graphs and Super Strongly Perfect Graphs.

Full Text:

PDF

References


Mary Jeya Jothi. R, Amutha. A, “Contributions to a Characterization of the structure of Super Strongly Perfect Graphs”, Proceedings of National Conference on Recent Developments in Mathematics and its Applications (NCRDMA), SRM University, Chennai, (287 – 293), (2011).

Mary Jeya Jothi. R, Amutha. A, “On Super Strongly Perfect Graphs”, International Journal of Computers, Mathematical Sciences and Applications, (195-201), 2009.

Stephan Olariu, “A Decomposition for strongly perfect graphs”, Journal of Graph Theory, vol.13, (301 – 311), (2006).

Paul D. Manuel, Bharati Rajan, Indra Rajasingh, and Amutha Alaguvel. “Tree Spanners Cayley Graphs, and Diametrically Uniform Graphs”, Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, vol.2880, (334–345), (2003).

West, D. B. “Introduction to Graph Theory, 2nd ed. ”, Englewood Cliffs, NJ Prentice-Hall, (2000).

Teresa W. Haynes, Stephan T. Hedetniemi, Peter J. Slater, “ Fundamentals of Domination in graphs”, MarcelDekkerinc, (1998).

Harary, F. “Planarity”, Ch. 11 in Graph Theory. Reading, MA Addison-Wesley, (102 – 125), (1994).

Skiena. S, “Implementing Discrete Mathematics”, Combinatorics and Graph Theory with Mathematica, Addison-Wesley, (1990).

Füredi, Z, “The number of maximal independent sets in connected graphs”, Journal of Graph Theory, vol.11, (463 – 470), (1987).

Chartrand, G. “Directed Graphs as Mathematical Models”, §1.5 in Introductory Graph Theory, New York, (16–190), (1985).

Berge. C, Duchet. P, “Strongly perfect graphs”, Ann. of Discr. Math., vol. 21, (57 – 61), (1984).

Berge. D, “Stochastic graphs and strongly perfect graphs”, a survey. Proceedings of the Seminar on Combinatorics and Applications, India, (60 – 65), (1982).

Ravindra. G, Parthasarathy. R, “Perfect product graphs, strongly and co-strongly perfect graphs”, Disc. Maths, vol. 20, (177 – 186), (1977).

Wilson, R. J. “Introduction to Graph Theory”, London Longman, (1975).

Alba, Richard D, “A graph-theoretic definition of a sociometric clique”, Journal of Mathematical Sociology, vol. 3, (113 – 126), (1973).

Lovász, Laszlo, “A characterization of perfect graphs”, Journal of Combinatorial Theory, Series B 13, (95 – 98), (1972).

Berge. Claude, “Perfect graphs”, Six Papers on Graph Theory, Indian Statistical Institute, Calcutta, vol. 61, (1 – 21), (1963).

Tutte, W. T. “A Theory of 3-Connected Graphs”, Indag. Math., vol. 23, (441–455),(1961).




DOI: http://dx.doi.org/10.36039/AA042011011

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.