Exponential domination in subcubic graphs

Authors Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

Publication date 18 January 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01398, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p42

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cage cubic graph domination exponential domination girth subcubic graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if

S

is a set of vertices of a graph

G

, then

S

is an exponential dominating set of

G

if

s u m l i m i t s_{v i n S} l e f t (f r a c 12 i g h t)^{{m d i s t}_{(G, S)} (u, v) - 1} g e q 1

for every vertex

u

in

V (G) s e t m i n u s S

, where

{m d i s t}_{(G, S)} (u, v)

is the distance between

u i n V (G) s e t m i n u s S

and

v i n S

in the graph

G - (S s e t m i n u s v)

. The exponential domination number

g a m m a_{e} (G)

of

G

is the minimum order of an exponential dominating set of

G

. In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If

G

is a connected subcubic graph of order

n (G)

, then

frac{n(G)}{6log_2(n(G)+2)+4}leq gamma_e(G)leq frac{1}{3}(n(G)+2).

For every

e p s i l o n > 0

, there is some

g

such that

g a m m a_{e} (G) l e q e p s i l o n n (G)

for every cubic graph

G

of girth at least

g

. For every

0 < a l p h a < f r a c 2 3 l n (2)

, there are infinitely many cubic graphs

G

with

g a m m a_{e} (G) l e q f r a c 3 n (G) l n (n (G))^{a l p h a}

. If

T

is a subcubic tree, then

g a m m a_{e} (T) g e q f r a c 16 (n (T) + 2) .

For a given subcubic tree,

g a m m a_{e} (T)

can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.

Review text

Summary: As a natural variant of domination in graphs, \textit{P. Dankelmann} et al. [Discrete Math. 309, No. 19, 5877--5883 (2009; Zbl 1191.05070)] introduced exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if \(S\) is a set of vertices of a graph \(G\), then \(S\) is an exponential dominating set of \(G\) if \(\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{\mathrm{dist}_{(G,S)}(u,v)-1}\geq 1\) for every vertex \(u\) in \(V(G)\setminus S\), where \(\mathrm{dist}_{(G,S)}(u,v)\) is the distance between \(u\in V(G)\setminus S\) and \(v\in S\) in the graph \(G-(S\setminus \{ v\})\). The exponential domination number \(\gamma_e(G)\) of \(G\) is the minimum order of an exponential dominating set of \(G\).{ }In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If \(G\) is a connected subcubic graph of order \(n(G)\), then \[ \frac{n(G)}{6\log_2(n(G)+2)+4}\leq \gamma_e(G)\leq \frac{1}{3}(n(G)+2). \] For every \(\varepsilon0\), there is some \(g\) such that \(\gamma_e(G)\leq \varepsilon n(G)\) for every cubic graph \(G\) of girth at least \(g\). For every \(0\alpha\frac{2}{3\ln(2)}\), there are infinitely many cubic graphs \(G\) with \(\gamma_e(G)\leq \frac{3n(G)}{\ln(n(G))^{\alpha}}\). If \(T\) is a subcubic tree, then \(\gamma_e(T)\geq \frac{1}{6}(n(T)+2).\) For a given subcubic tree, \(\gamma_e(T)\) can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Exponential domination in subcubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q504979)