DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

X.-G. Chen, Y.-F. Wang and X.-F. Wu

Title:

Hereditary equality of domination and exponential domination in subcubic graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-10-11, Revised: 2019-05-13, Accepted: 2019-05-13, https://doi.org/10.7151/dmgt.2237

Abstract:

Let $\gamma(G)$ and $\gamma_{e}(G)$ denote the domination number and exponential domination number of graph $G$, respectively. Henning et al., in [Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory 38 (2018) 275–285] gave a conjecture: There is a finite set $\mathscr{F}$ of graphs such that a graph $G$ satisfies $\gamma(H)=\gamma_{e}(H)$ for every induced subgraph $H$ of $G$ if and only if $G$ is $\mathscr{F}$-free. In this paper, we study the conjecture for subcubic graphs. We characterize the class $\mathscr{F}$ by minimal forbidden induced subgraphs and prove that the conjecture holds for subcubic graphs.

Keywords:

dominating set, exponential dominating set, subcubic graphs

PDF
Close