Secure Triple Connected Domination Number of a Graph

K. Ameenal Bibi, S.E. Annie Jasmine


Secure domination is a well-studied concept [3, 4, 5]. In this domination, a vertex outside has the chance of coming inside the dominating set by replacing an element of the set without affecting domination. This idea is combined with the concept of triple connected domination, by considering a path between any three vertices of a graph [10, 11, 12], to introduce a new parameter called secure triple connected domination. A secure dominating set \(S\) of \(V\) of a nontrivial graph \(G\) is said to be secure triple connected dominating set, if the induced sub graph \(\langle S\rangle\) is triple connected. Among all the secure triple connected dominating sets of the graph \(G\), a set having the minimum cardinality is called the secure triple connected domination number denoted by \(\gamma_{stc}\) of \(G\). We have determined the exact values of secure triple connected domination number for some standard graphs and obtained bounds for this new parameter. NORDHAUS-GADDUM type results and the relationship of this parameter with other graph theoretical parameters are also discussed.


Domination number; Secure domination number; Triple connected domination number; Secure connected domination number; Secure triple connected dominating set; Secure triple connected domination number

Full Text:



J.A. Bondy and U.S.R. Murty, Graph Theory, Springer (2008).

A.P. Burger, M.A. Henning and J.H. Yan Vuren, Vertex cover and secure domination in graphs, Quaestiones Mathematicae 31(2) (2008), 163 – 171.

A.G. Cabaro, S.S. Canoy Jr. and I.S. Aniversario, Secure connected domination in a graph, International Journal of Mathematical Analysis 8(42) (2014), 2065 – 2074.

E. Castillans, R.A. Ugbinada and S. Caney Jr., Secure domination in the join of graphs, Applied Mathematical Sciences, Applied Mathematical Science 8 (105), 5203 – 5211.

E.J. Cockayne, Irredendance, secure domination & maximum degree in tree, Discrete Math. 307 (2007), 12 – 17.

E.J. Cockayne, O. Favaran and C.M. Mynhardt, Secure domination, weak roman domination and forbidden sub graphs, Bull. Inst. Combin. Appl. 39 (2003), 87 – 100.

E.J. Cokayne and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211 – 219.

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York (1998).

T.W. Haynes, T. Stephen, Hedetniemi and P.S. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, New York (1990).

G. Mahadevan, S. Avadayappan, J. Paulraj Joseph, B. Ayisha and T. Subramanian, Complementary triple connected domination number of a graph, Advances and Applications in Discrete Mathematics 12(1) (2013), 39 – 54.

G. Mehedevan, A. Selvam and J. Paulraj Joseph and T. Subramanian, Triple connected domination number of a graph, International Journal of Mathematical Combinatorics 3 (2012), 93 – 104.

E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175 – 177.

J. Paulraj Joseph and S. Arumugan, Domination and connectively in graphs, International Journal of Management and systems 8(3) (1992), 233 – 236.

J. Paulraj Joseph, M.K. Angel Jebitha, P. Chitra Devi and G. Sudhana, Triple connected graphs, Indian Journal of Mathematics Mathematical Sciences 8(1) (2012), 61 – 75.

E. Sampathkumar and H.B. Wailkar, The connected domination number of a graph, J. Math. Phys. Sci. 13(6) (1979), 607 – 613.

S. Sivakumar and N.D. Soner, Triple connected equitable domination in graphs, International Journal of Mathematical Archive 4(5) (2012), 90 – 97.


eISSN 0975-5748; pISSN 0974-875X