Independence Saturation In Complementary Product Types of Graphs

Abstract

The independence saturation number  of a graph  is defined as , where  is the maximum cardinality of an independent set that contains vertex . Let  be the complement graph of . Complementary prisms are the subset of complementary product graphs. The complementary prism  of  is the graph formed from the disjoint union of  and  by adding the edges of a perfect matching between the corresponding vertices of  and . In this paper, the independence saturation in complementary prisms are considered, then the complementary prisms with small independence saturation numbers are characterized.

Keywords

• Complementary prisms,graph theory,independence,independence saturation,network topology

References

1. [1] Korshunov, A.D. Coefficient of Internal Stability of Graphs. Cybernetics. 1974; 10, 19-33.
2. [2] Bomze, I.; Budinich, M.; Pardalos, P.; Pelillo, M. The Maximum Clique Problem. Handbook of Combinatorial Optimization, Supplement Volume A; Du, D., Pardalos, P., Eds.; Kluwer Academic Press: 1999.
3. [3] Subramanian, M. Studies in Graph Theory-Independence Saturation in Graphs, Ph.D thesis, Manonmaniam Sundaranar University, 2004.
4. [4] West, D.B. Introduction to Graph Theory; Prentice Hall, NJ, 2001.
5. [5] Buckley, F.; Harary, F. Distance in Graphs; Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, 1990.
6. [6] Haynes, T.W.; Henning, M.A.; Slater, P.J.; Merwe, V.D. The Complementary Product of Two Graphs. Bull. Instit. Combin. Appl. 2007; 51, 21-30.
7. [7] Arumugam, S.; Subramanian, M. Independence Satura-tion and Extended Domination Chain in graphs. AKCE J. Graphs. Combin. 2007; 4, 59-69.
8. [8] Gongora, J.A.; Haynes, T.W.; Jum, E. Independent Domi-nation in Complementary Prisms. UTILITAS MATHEMAT-ICA. 2013; 91, 3-12.

9. [9] Aytaç, A.; Turacı, T. Strong Weak Domination in Com-plementary Prisms. Dynamics of Continuous, Discrete & Impulsive Systems Series B: Applications & Algorithms. 2015; 22(2b), 85-96.
10. [10] Gölpek, T.H.; Turacı, T.; Coskun, B. On The Average Lower Domination Number and Some Results of Comple-mentary Prisms and Graph Join. Journal of Advanced Re-search in Applied Mathematics. 2015; 7(1), 52-61.
11. [11] Desormeaux, W.J.; Haynes, T.W.; Vaughan, L. Double Domination in Complementray Prisms. UTILITAS MATHEMATICA. 2013; 91, 131-142.
12. [12] Desormeaux, W.J.; Haynes, T.W. Restrained Domina-tion in Complementray Prisms. UTILITAS MATHEMATI-CA. 2011; 86, 267-278.
13. [13] Kazemi, A.P. k-Tuple Total Restrained Domination in Complementary Prisms. ISRN Combinatorics. 2013; doi:10.1155/2013/984549.
14. [14] Chaluvaraju, B.; Chaitra, V. Roman domination in Complementary Prism Graphs. International J. Math. Combin. 2012; 2, 24-31
15. [15] Muthulakshmi, T.; Subramanian, M. Independence saturation number of some classes of graphs. Far East Jour-nal of Mathematical Sciences. 2014; 86(1), 11-21.
16. [16] Berberler, Z.N.; Berberler, M.E. Independently Saturat-ed Graphs. TWMS J. APP. ENG. MATH. Accepted. 2017.
17. [17] Haynes, T.W.; Henning, M.A.; Merwe, V.D. Domination and total domination in complementary prisms. J Comb Optim. 2009; 18, 23-37.
18. [18] Holmes, K.R.S.; Koessler, D.R.; Haynes, T.W. Locating-domination in complementary prisms. J Comb Math Comb Comput. 2010; 72, 163-171.