Independence Saturation In Complementary Product Types of Graphs

Year 2017, Volume: 13 Issue: 2, 325 - 331, 30.06.2017

Zeynep Nihan Berberler Murat Erşen Berberler

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] Korshunov, A.D. Coefficient of Internal Stability of Graphs. Cybernetics. 1974; 10, 19-33.
• [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] Subramanian, M. Studies in Graph Theory-Independence Saturation in Graphs, Ph.D thesis, Manonmaniam Sundaranar University, 2004.
• [4] West, D.B. Introduction to Graph Theory; Prentice Hall, NJ, 2001.
• [5] Buckley, F.; Harary, F. Distance in Graphs; Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, 1990.
• [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] Arumugam, S.; Subramanian, M. Independence Satura-tion and Extended Domination Chain in graphs. AKCE J. Graphs. Combin. 2007; 4, 59-69.
• [8] Gongora, J.A.; Haynes, T.W.; Jum, E. Independent Domi-nation in Complementary Prisms. UTILITAS MATHEMAT-ICA. 2013; 91, 3-12.
• [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] 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] Desormeaux, W.J.; Haynes, T.W.; Vaughan, L. Double Domination in Complementray Prisms. UTILITAS MATHEMATICA. 2013; 91, 131-142.
• [12] Desormeaux, W.J.; Haynes, T.W. Restrained Domina-tion in Complementray Prisms. UTILITAS MATHEMATI-CA. 2011; 86, 267-278.
• [13] Kazemi, A.P. k-Tuple Total Restrained Domination in Complementary Prisms. ISRN Combinatorics. 2013; doi:10.1155/2013/984549.
• [14] Chaluvaraju, B.; Chaitra, V. Roman domination in Complementary Prism Graphs. International J. Math. Combin. 2012; 2, 24-31
• [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] Berberler, Z.N.; Berberler, M.E. Independently Saturat-ed Graphs. TWMS J. APP. ENG. MATH. Accepted. 2017.
• [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] Holmes, K.R.S.; Koessler, D.R.; Haynes, T.W. Locating-domination in complementary prisms. J Comb Math Comb Comput. 2010; 72, 163-171.