Computing the split domination number of grid graphs

V. R. Girish, P. Usha

Abstract


A set D - V is a dominating set of G if every vertex in V - D is adjacent to some vertex in D. The dominating number γ(G) of G is the minimum cardinality of a dominating set D. A dominating set D of a graph G = (V;E) is a split dominating set if the induced graph (V - D) is disconnected. The split domination number γs(G) is the minimum cardinality of a split domination set. In this paper we have introduced a new method to obtain the split domination number of grid graphs by partitioning the vertex set in terms of star graphs and also we have
obtained the exact values of γs(Gm;n); m ≤ n; m,n ≤ 24:


Keywords


Domination number;split domination; grid graph

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2021.5.1.1

References

D. Goncalves, A. Pinlou, M. Rao and S. Thomasse, The domination of grid graph, SIAM J. Discrete Math. 25 (3) (2011), 1443-1453.

F. Harary, Graph Theory, Addison-wesley. reading Mass (1969).

V. R. Kulli, B. Janikiram, The split domination number of a graph, Graph Theory Notes of New York Academy of Sciences. XXXII (1997),16-19.

S. Alanko, A. Isopoussu, P. Ostergard, and V. Pettersson, Computing the domination number of grid graphs, Electron. J. Combin. 18 (2011), P141.

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


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

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

View IJC Stats