Trivially Extendable Graphs

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

1. Hartnell,B. and Plummer,M. D., (1996), On 4-Connected Claw-Free Well-Covered Graph, Discrete Applied Mathematics 64, pp. 57-65.
2. Randeratha,B. and Volkmann,L., (1994), A Characterization of Well- Covered block-cactus graphs, Australian Journal of Combinatorics 9, pp. 307-314.
3. Burce,E. S. agan and Vatter,V. R., (2003), Maximal and maximum independent sets in Graphs with at most cycles, Michigan State University.
4. Tankus,D. and Tarsh,M., (1992), Well covered claw-free graphs, Journal of Combinatorial Theory, Series B 66, pp. 293-302.
5. Harary,F., (1972) Graph Theory, Addison Wesley, Reading Mass.
6. Haynes,T. W., Hedetniemi,S. T. and Slater,P. J., (1998), Fundamentals of Domination in Graphs, Marcel Dekker Inc..
7. 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.
8. 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.

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