Independent strong domination in complementary prisms

Zeynep Nihan Berberler, Murat Ersen Berberler

Abstract


Let G = (V, E) be a graph and u,v ∈ V. Then, u strongly dominates  v if (i) uv ∈ E  and (ii) deg(u) ≥ deg(v). A set D ⊂ V  is a strong-dominating set of  G  if every vertex in V-D is strongly dominated by at least one vertex in D. A set D ⊆ V  is an independent set if no two vertices of D  are adjacent. The independent strong domination number is(G) of a graph G is the minimum cardinality of a strong dominating set which is independent. Let Ġ   be the complement of a graph G. The complementary prism GĠ  of G  is the graph formed from the disjoint union of G  and  Ġ by adding the edges of a perfect matching between the corresponding vertices of G and Ġ. In this paper, we consider the independent strong domination in complementary prisms, characterize the complementary prisms with small independent strong domination numbers, and investigate the relationship between independent strong domination number and the distance-based parameters.


Keywords


domination, independent strong domination, complementary prisms, corona product

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.1

References

C. Cooper, R. Klasing and M. Zito, Lower bounds and algorithms for dominating sets in web graphs, Internet Math. 2 (2005), 275–300.

D. Rautenbach, Bounds on the strong domination number, Discrete Math. 215 (2000), 201– 212.

D. Rautenbach, The influence of special vertices on the strong domination, Discrete Math. 197/198 (1999), 683–690.

D. Rautenbach and V.E. Zverovich, Perfect graphs of strong domination and independent strong domination, Discrete Math. 226 (2001), 297–311.

E. Sampathkumar and L. Pushpa Latha, Strong weak domination and domination balance in a graph, Discrete Math. 161 (1996), 235–242.

E. Vatandoost and F. Ramezani, On the domination and signed domination numbers of zero- divisor graph, Electron. J. Graph Theory Appl. 4 (2) (2016), 148–156.

E. Vatandoost and M. Khalili, Domination number of the non-commuting graph of finite groups, Electron. J. Graph Theory Appl. 6 (2) (2018), 228–237.

F. Buckley and F. Harary, Distance in Graphs. Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA (1990).

F. Dai and J. Wu, On constructing k-connected k-dominating sets in wireless ad-hoc and sensor networks, J. Parall. Distrib. Comput. 66 (7) (2006), 947–958.

G. Chartrand and L. Lesniak, Graphs and Digraphs, Fourth Edition, Chapman & Hall, London (2005).

G.S. Domke, J.H. Hattingh, L.R. Markus and E. Ungener, On parameters related to strong and weak domination in graphs, Discrete Math. 258 (2002), 1–11.

J. Alber, N. Betzler and R. Niedermeier, Experiments on data reduction for optimal domina-tion in networks, Ann. Oper. Res. 146 (2006), 105–117.

J.H. Hattinghand M.A.Henning, On strong domination in graphs, J. Combin. Math. Combin. Comput. 26 (1998), 33–42.

M.H. Akhbari and N.J. Rad, Bounds on weak and strong total domination number in graphs, Electron. J. Graph Theory Appl. 4 (1) (2016), 111–118.

T.W. Haynes, M.A. Henning, P.J. Slater and L.C. Van Der Merwe, The complementary product of two graphs, Bull. Instit. Combin. Appl. 51 (2007), 21–30.

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

T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, (1998).

V. Aytac ̧ and Z.N. Berberler, Average independent domination in complementary prisms, Bulletin of the International Mathematical Virtual Institute 10 (1) (2020), 157–164.

Z.N. Berberler, Strong independent saturation in complementary prims, Mathematical Sciences and Applications E-Notes 6 (1) (2018), 99–105.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats