Pith. sign in

On the total $(k,r)$-domination number of random graphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

A subset $S$ of a vertex set of a graph $G$ is a total $(k,r)$-dominating set if every vertex $u \in V(G)$ is within distance $k$ of at least $r$ vertices in $S$. The minimum cardinality among all total $(k,r)$-dominating sets of $G$ is called the total $(k,r)$-domination number of $G$, denoted by $\gamma^{t}_{(k,r)}(G)$. We previously gave an upper bound on $\gamma^{t}_{(2,r)}(G(n,p))$ in random graphs with non-fixed $p \in (0,1)$. In this paper we generalize this result to give an upper bound on $\gamma^{t}_{(k,r)}(G(n,p))$ in random graphs with non-fixed $p \in (0,1)$ for $k\geq 3$ as well as present an upper bound on $\gamma^{t}_{(k,r)}(G)$ in graphs with large girth.

citation-role summary

background 1

citation-polarity summary

fields

cs.CC 1

years

2024 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

Parameterized Complexity of (d,r)-Domination via Modular Decomposition

cs.CC · 2024-12-20 · conditional · novelty 6.0

The authors prove that (d,r)-domination is fixed-parameter tractable by modular-width plus demand, admits polynomial compressions by modular-width and iterated type partition number plus demand, and admits a polynomial kernel by neighborhood diversity plus demand.

citing papers explorer

Showing 1 of 1 citing paper.

  • Parameterized Complexity of (d,r)-Domination via Modular Decomposition cs.CC · 2024-12-20 · conditional · none · ref 33 · internal anchor

    The authors prove that (d,r)-domination is fixed-parameter tractable by modular-width plus demand, admits polynomial compressions by modular-width and iterated type partition number plus demand, and admits a polynomial kernel by neighborhood diversity plus demand.