Trivially Extendable Graphs

Year 2015, Volume: 5 Issue: 2, 307 - 313, 01.12.2015

- K.angaleeswari - P.sumathi - V.swaminathan

Abstract

Let G be a simple graph. Let k be a positive integer. G is said to be k-extendable if every independent set of cardinality k is contained in a maximum independent set of G. G is said to be trivially extendable if G is not k-extendable for 1 ≤ k ≤ β0 G − 1 . A well covered graph is one in which every maximal independent set is maximum. Study of k-extendable graphs has been made in [7,8,9]. In this paper a study of trivially extendable graphs is made. Characterization of graphs with β0 G = n − 3 and which is trivially extendable has been done. Similarly graphs with β0 G = n − 2 is also studied for trivial extensibility

Keywords

Berge graph, Extensibility in graphs, Trivially extendable graphs

References

• Hartnell,B. and Plummer,M. D., (1996), On 4-Connected Claw-Free Well-Covered Graph, Discrete Applied Mathematics 64, pp. 57-65.
• Randeratha,B. and Volkmann,L., (1994), A Characterization of Well- Covered block-cactus graphs, Australian Journal of Combinatorics 9, pp. 307-314.
• Burce,E. S. agan and Vatter,V. R., (2003), Maximal and maximum independent sets in Graphs with at most cycles, Michigan State University.
• Tankus,D. and Tarsh,M., (1992), Well covered claw-free graphs, Journal of Combinatorial Theory, Series B 66, pp. 293-302.
• Harary,F., (1972) Graph Theory, Addison Wesley, Reading Mass.
• Haynes,T. W., Hedetniemi,S. T. and Slater,P. J., (1998), Fundamentals of Domination in Graphs, Marcel Dekker Inc..
• Angaleeswari,K., Sumathi,P. and Swaminathan,V., (2013), Extensibility in Graph with Unique Max- imum Independent Set, Global Journal of Pure and Applied Mathematics, ISSN 0973-1768, Volume 9, pp. 567-574.
• Angaleeswari,K., Sumathi,P. and Swaminathan,V., (2014), k-extendable graphs and Weakly k- extendable graphs, Journal of Modern Science, ISSN No.2277-7628, Volume 1, pp. 61-70.
• Angaleeswari,K., Sumathi,P. and Swaminathan,V., (2015), k-extensibility in Graphs,International Journal of Pure and Applied Mathematics, ISSN:1311-8080, volume 101, No.5, pp. 801-809.