Independent domination of gridsDiscrete Mathematics

About

Authors
Simon Crevals, Patric R.J. Östergård
Year
2015
DOI
10.1016/j.disc.2015.02.015
Subject
Discrete Mathematics and Combinatorics / Theoretical Computer Science

Similar

RELATIONSHIP BETWEEN OCULAR DOMINANCE AND FIELD-DEPENDENCE/INDEPENDENCE

Authors:
VEZIO RUGGIERI, CHIARA BERGERONE, ALBERTO CEI, DAVIDE CERIDONO
1980

Democracy-Independence Trade-Off in Oscillating Dendrites and Its Implications for Grid Cells

Authors:
Michiel W.H. Remme, Máté Lengyel, Boris S. Gutkin
2010

Max born medal and prize

Authors:
The Institute of Physics
1979

Front Matter: Volume 9152

Authors:
Proceedings of SPIE
2014

Text

Discrete Mathematics 338 (2015) 1379–1384

Contents lists available at ScienceDirect

Discrete Mathematics journal homepage: www.elsevier.com/locate/disc

Independent domination of grids

Simon Crevals ∗, Patric R.J. Östergård

Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076 Aalto, Finland a r t i c l e i n f o

Article history:

Received 31 January 2013

Received in revised form 5 September 2014

Accepted 24 February 2015

Keywords:

Grid graph

Independent domination a b s t r a c t

Let im,n denote the minimum size of an independent dominating set in them-by-n grid. In this article a dynamic programming algorithm is described that computes im,n for fixed m and arbitrary n. For m < 16, the algorithm is used to determine im,n as a function of n. For m, n ≥ 16, it is proved that im,n = ⌊(m+ 2)(n+ 2)/5⌋− 4 by constructing corresponding independent dominating sets and by applying results on the minimum size of dominating sets. Thus the independent domination number is now known for all grids. © 2015 Elsevier B.V. All rights reserved. 1. Introduction

Let [k] denote the set of the first k positive integers. The m-by-n grid, denoted Pm,n, is the graph with vertex set {vi,j: (i, j) ∈ [m] × [n]} and edge set {vi,jvi′,j′ : |i − i′| + |j − j′| = 1}. Thus, Pm,n is isomorphic to the Cartesian product

PmPn, where Pm and Pn are paths of lengthm− 1 and n− 1, respectively.

A dominating set of a graph G is a subset S ⊆ G(V ) such that every vertex outside S is adjacent to at least one vertex in

S. The domination number γ (G) of a graph G is the minimum size of a dominating set of G. When G is Pm,n, we denote the domination number γ (G) by γm,n. An independent dominating set of a graph is a dominating set that is also an independent set, and the independent domination number i(G) of a graph G is the minimum size of an independent dominating set of G.

When G is Pm,n, we denote the independent domination number i(G) by im,n.

The study of the domination number of grids started in the 1980s. Early work focused on combinatorial and computational methods for establishing γm,n with specific parameters m and n [1,11,10,14,15,17,20] as well as for a fixed (small) m and arbitrary n [3,12,18]. Studies of general lower and upper bounds on γm,n include [2,4–6,9]. Chang [2] showed that γm,n ≤  (m+ 2)(n+ 2) 5  − 4 (1) when m, n ≥ 8 and conjectured that equality holds when m, n ≥ 16. This conjecture was finally proved by Gonçalves et al. [8] in 2011 using ideas similar to those proposed by Guichard [9].

The resolution of the problem of determining the domination number of grids is a catalyst for attacking variants of that problem. As far as we know, no studies on the independent domination number of grids have been carried out so far. A general survey of independent domination of graphs can be found in [7].

Since i(G) (or, in general, the minimum size of a dominating set with any additional properties) is bounded from below by γ (G), finding an independent dominating set of size γ (G) implies i(G) = γ (G). This idea is central in the current paper, where im,n is determined for all m and n. General studies of graphs having equal domination and independent domination numbers include [13,16,19]. ∗ Corresponding author.

E-mail addresses: simon.crevals@aalto.fi (S. Crevals), patric.ostergard@aalto.fi (P.R.J. Östergård). http://dx.doi.org/10.1016/j.disc.2015.02.015 0012-365X/© 2015 Elsevier B.V. All rights reserved. 1380 S. Crevals, P.R.J. Östergård / Discrete Mathematics 338 (2015) 1379–1384

In Section 2.1 we give a brief introduction to (min,+)-semirings, which are applied in Section 2.2 to give an algorithm for determining im,n for fixedm and arbitrary n. In Section 2.3, we apply the algorithm to obtain im,n form < 16 and compare the domination and independent domination numbers in that case. In Section 3 we construct infinite families of independent dominating sets, which show that the upper bound in (1) is also an upper bound for the independent domination number whenm, n ≥ 16. Consequently, im,n equals the right side of (1) whenm, n ≥ 16. Thus the independent domination number is now known for all grids. 2. Formulae form < 16 2.1. (min,+)-Semirings

An algorithm that uses (min, +)-semirings to compute formulae for the independent domination number of grids will be presented in Section 2.2; this algorithm is developed from results by Spalding [18].

Two operators on the real numbers, including infinity, define (min, +)-semirings: , representing minimization, and , representing standard addition. The symbol  is used to indicate addition in the semiring because it plays the role of multiplication in the distributive law. Both operators are commutative and associative, and both have an identity element: 0 for  and∞ for . They also satisfy the distributive property: a  (b  c) = (a  b)  (a  c), since a+min(b, c) = min(a+ b, a+ c). The operation  is defined on matrices as (A  B)i,j = nk=1 ai,k  bk,j, where A = (ai,j) and B = (bi,j) are, respectively,m× n and n× pmatrices. For square matrices Ar is recursively defined in the usual way: A1 = A and Ar = AAr−1. The operation between a scalar c and amatrix A is defined by (cA)i,j = cai,j. 2.2. Algorithm

Wewill nowuse (min,+)-semirings to find formulae for the independent domination number im,n for fixedm. To describe the algorithm we must first define the concepts of state and state transition matrix. The idea is that the jth state describes for each vi,j with 1 ≤ i ≤ m whether it is a dominating vertex, or a vertex dominated by some vi′,j′ , j′ ≤ j, or a vertex only dominated by vi,j+1.

Definition 2.1. Let D be an independent dominating set of Pm,n. Define S to be them× nmatrix with entries from {0, 1, 2} such that si,j = 0, if vi,j ∈ D 1, if vi,j ∉ D and {vi−1,j, vi+1,j, vi,j−1} ∩ D ≠ ∅ 2, otherwise.