pith. sign in

arxiv: 1211.5742 · v1 · pith:UJUEXKRInew · submitted 2012-11-25 · 🧮 math.CO

Trees with Maximum p-Reinforcement Number

classification 🧮 math.CO
keywords numbergraphtreesadditionattainingboundcardinalitycharacterize
0
0 comments X
read the original abstract

Let $G=(V,E)$ be a graph and $p$ a positive integer. The $p$-domination number $\g_p(G)$ is the minimum cardinality of a set $D\subseteq V$ with $|N_G(x)\cap D|\geq p$ for all $x\in V\setminus D$. The $p$-reinforcement number $r_p(G)$ is the smallest number of edges whose addition to $G$ results in a graph $G'$ with $\g_p(G')<\g_p(G)$. Recently, it was proved by Lu et al. that $r_p(T)\leq p+1$ for a tree $T$ and $p\geq 2$. In this paper, we characterize all trees attaining this upper bound for $p\geq 3$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.