2020•arXiv (Cornell University)Open access

A note on semitotal domination in graphs

Wei Zhuang

Open full text 0 citations

Abstract

A set $S$ of vertices in $G$ is a semitotal dominating set of $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance $2$ of another vertex of $S$. The \emph{semitotal domination number}, $γ_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. The \emph{semitotal domination multisubdivision number} of a graph $G$, $msd_{γ_{t2}}(G)$, is the minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the semitotal domination number of $G$. In this paper, we show that $msd_{γ_{t2}}(G)\leq 3$ for any graph $G$ of order at least $3$, we also determine the semitotal domination multisubdivision number for some classes of graphs and characterize trees $T$ with $msd_{γ_{t2}}(T)=3$. On the other hand, we know that $γ_{t2}(G)$ is a parameter that is squeezed between domination number, $γ(G)$ and total domination number, $γ_t(G)$, so for any tree $T$, we investigate the ratios $\frac{γ_{t2}(T)}{γ(T)}$ and $\frac{γ_t(T)}{γ_{t2}(T)}$, and present the constructive characterizations of the families of trees achieving the upper bounds.

Open-access reader

About this research paper

What this paper is about

A set $S$ of vertices in $G$ is a semitotal dominating set of $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance $2$ of another vertex of $S$. The \emph{semitotal domination number}, $γ_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. The \emph{semitotal domination multisubdivision number} of a graph $G$, $msd_{γ_{t2}}(G)$, is the minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the semitotal domination number of $G$. In this paper, we show that $msd_{γ_{t2}}(G)\leq 3$ for any graph $G$ of order at least $3$, we also determine the semitotal domination multisubdivision number for some classes of graphs and characterize trees $T$ with $msd_{γ_{t2}}(T)=3$. On the other hand, we know that $γ_{t2}(G)$ is a parameter that is squeezed between domination number, $γ(G)$ and total domination number, $γ_t(G)$, so for any tree $T$, we investigate the ratios $\frac{γ_{t2}(T)}{γ(T)}$ and $\frac{γ_t(T)}{γ_{t2}(T)}$, and present the constructive characterizations of the families of trees achieving the upper bounds.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

A set $S$ of vertices in $G$ is a semitotal dominating set of $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance $2$ of another vertex of $S$. The \emph{semitotal domination number}, $γ_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. The \emph{semitotal domination multisubdivision number} of a graph $G$, $msd_{γ_{t2}}(G)$, is the minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the semitotal domination number of $G$. In this paper, we show that $msd_{γ_{t2}}(G)\leq 3$ for any graph $G$ of order at least $3$, we also determine the semitotal domination multisubdivision number for some classes of graphs and characterize trees $T$ with $msd_{γ_{t2}}(T)=3$. On the other hand, we know that $γ_{t2}(G)$ is a parameter that is squeezed between domination number, $γ(G)$ and total domination number, $γ_t(G)$, so for any tree $T$, we investigate the ratios $\frac{γ_{t2}(T)}{γ(T)}$ and $\frac{γ_t(T)}{γ_{t2}(T)}$, and present the constructive characterizations of the families of trees achieving the upper bounds.

Key concepts: Mathematics, Combinatorics

Related papers

Back to paper searchBrowse research topicsOriginal source
A note on semitotal domination in graphs — Research Paper | ScholarLens