On the Secure Total Domination Number of Graphs

Abstract

A total dominating set D of a graph G is said to be a secure total dominating set if for every vertex $u\in V\left(G\right)\backslash D$, there exists a vertex $v\in D$, which is adjacent to u, such that $(D\backslash \{v\left\}\right)\cup \left\{u\right\}$ is a total dominating set as well. The secure total domination number of G is the minimum cardinality among all secure total dominating sets of G. In this article, we obtain new relationships between the secure total domination number and other graph parameters: namely the independence number, the matching number and other domination parameters. Some of our results are tight bounds that improve some well-known results.

1. Introduction

The following approach to the protection of a graph was proposed by Cockayne et al. [1]. Suppose that one or more entities are stationed at some of the vertices of a graph G and that an entity at a vertex can deal with a problem at any vertex in its closed neighbourhood. In general, an entity could consist of an observer, a robot, a guard, a legion, and so on. Informally, we say that G is protected under a given placement of entities if there exists at least one entity available to handle a problem at any vertex. The simplest cases of graph protection are those in which you can locate at most one entity per vertex. In such a case, the set of vertices containing the entities is said to be a dominating set.

In a graph $G=\left(V\right(G),E(G\left)\right)$, a vertex dominates itself and its neighbours. A subset $S\subseteq V\left(G\right)$ is said to be a dominating set of G if S dominates every vertex of G, while S is said to be a total dominating set if every vertex $v\in V\left(G\right)$ is dominated by at least one vertex in $S\backslash \left\{v\right\}$. As usual, the neighbourhood of a vertex $v\in V\left(G\right)$ will be denoted by $N\left(v\right)$. Now, a set $S\subseteq V\left(G\right)$ is said to be a secure (total) dominating set if S is a (total) dominating set and for every $v\in V\left(G\right)\backslash S$ there exists $u\in N\left(v\right)\cap S$ such that $(S\cup \{v\left\}\right)\backslash \left\{u\right\}$ is a (total) dominating set. In the case of secure (total) domination, the graph is deemed protected by a (total) dominating set and when an entity moves (to deal with a problem) to a neighbour not included in the (total) dominating set, the new set of entities obtained from the movement of the entity is a (total) dominating set which protects the graph as well.

The minimum cardinality among all dominating sets of G is the domination number of G, denoted by $\gamma \left(G\right)$. The total domination number, the secure domination number and the secure total domination number of G are defined by analogy, and are denoted by ${\gamma }_t\left(G\right)$, ${\gamma }_s\left(G\right)$ and ${\gamma }_{st}\left(G\right)$, respectively.

The domination number and the total domination number have been extensively studied. For instance, we cite the following books [2,3,4]. The secure domination number, which has been less studied, was introduced by Cockayne et al. in [1] and studied further in several works including [5,6,7,8,9,10], while the secure total domination number was introduced by Benecke et al. in [11] and studied further in [9,12,13,14].

In this work we study the relationships between the secure total domination number and other graph parameters. The article is organized as follows. In Section 2 we define key terms and additional notation. In Section 3 we show that ${\gamma }_{st}\left(G\right)\le \alpha \left(G\right)+\gamma \left(G\right),$ where $\alpha \left(G\right)$ denotes the independence number of G. Since $\gamma \left(G\right)\le \alpha \left(G\right)$, this result improves the bound ${\gamma }_{st}\left(G\right)\le 2\alpha \left(G\right)$ obtained in [14]. Section 4 is devoted to the study of relationships between the secure total domination number and other domination parameters. In particular, we outline some known results that become tools to derive new ones. Finally, in Section 5 we obtain several bounds on the secure total domination number in terms of the matching number and other graph parameters.

2. Some Additional Concepts and Notation

All graphs considered in this paper are finite and undirected, without loops or multiple edges. The minimum degree of a graph G will be denoted by $\delta \left(G\right)$ and the maximum degree by $\Delta \left(G\right)$. As usual, the closed neighbourhood of a vertex $v\in V\left(G\right)$ is denoted by $N\left[v\right]=N\left(v\right)\cup \left\{v\right\}$. We say that a vertex $v\in V\left(G\right)$ is a universal vertex of G if $N\left[v\right]=V\left(G\right)$. By analogy with the notation used for vertices, for a set $S\subseteq V\left(G\right)$, its open neighbourhood is the set $N\left(S\right)={\cup }_{v\in S}N\left(v\right)$, and its closed neighbourhood is the set $N\left[S\right]=N\left(S\right)\cup S$. We also define the following sets associated with $v\in V\left(G\right)$.

• The internal private neighbourhood of v relative to S is defined by

  $$ipn(v,S)=\{u\in S:N(u)\cap S=\{v\left\}\right\}.$$
• The external private neighbourhood of v relative to S is defined by

  $$epn(v,S)=\{u\in V(G)\backslash S:N(u)\cap S=\{v\left\}\right\}.$$
• The private neighbourhood of v relative to S is defined by

  $$pn(v,S)=ipn(v,S)\cup epn(v,S)=\{u\in V(G):N(u)\cap S=\{v\left\}\right\}.$$

The subgraph induced by $S\subseteq V\left(G\right)$ will be denoted by $\langle S\rangle$, while the graph obtained from G by removing all the vertices in $S\subseteq V\left(G\right)$ (and all the edges incident with a vertex in S) will be denoted by $G-S$. If H is a graph, then we say that a graph G is H-free if G does not contain any copy of H as an induced subgraph.

We denote the set of leaves of a graph G by $L\left(G\right)$, and the set of support vertices (vertices adjacent to leaves) by $S\left(G\right)$. The set of isolated vertices of $\langle V\left(G\right)\backslash \left(S\right(G)\cup L(G\left)\right)\rangle$ will be denoted by $I_G$.

We will use the notation $C_n$, $N_n$ and $P_n$ for cycle graphs, empty graphs and path graphs of order n, respectively.

Let $f:V\left(G\right)\to \{0,1,2\}$ be a function. For any $i\in \{0,1,2\}$ we define the subsets of vertices $V_i=\{v\in V\left(G\right):f\left(v\right)=i\}$ and we identify f with the three subsets of $V\left(G\right)$ induced by f. Thus, in order to emphasize the notation of these sets, we denote the function by $f(V_0,V_1,V_2)$. Given a set $X\subseteq V\left(G\right)$, we define $f\left(X\right)={\sum }_{v\in X}f\left(v\right)$, and the weight of f is defined to be $\omega \left(f\right)=f\left(V\left(G\right)\right)=|V_1|+2|V_2|$.

A (total) weak Roman dominating function is a function $f(V_0,V_1,V_2)$ satisfying that $V_1\cup V_2$ is (total) dominating set and for every vertex $v\in V_0$ there exists $u\in N\left(v\right)\cap (V_1\cup V_2)$ such that the function $f^{\prime }(V_0^{\prime },V_1^{\prime },V_2^{\prime })$, defined by $f^{\prime }\left(v\right)=1$, $f^{\prime }\left(u\right)=f\left(u\right)-1$ and $f^{\prime }\left(x\right)=f\left(x\right)$ whenever $x\in V\left(G\right)\backslash \{u,v\}$, satisfies that $V_1^{\prime }\cup V_2^{\prime }$ is (total) dominating set. Notice that $S\subseteq V\left(G\right)$ is a secure (total) dominating set if and only if there exits a (total) weak Roman dominating function $f(V_0,V_1,V_2)$ such that $V_2=\varnothing$ and $V_1=S$.

The weak Roman domination number, denoted by ${\gamma }_r\left(G\right)$, is the minimum weight among all weak Roman dominating functions on G. By analogy we define the total weak Roman domination number, which is denoted by ${\gamma }_{tr}\left(G\right)$. The weak Roman domination number was introduced by Henning and Hedetniemi [15] and studied further in several works including [7,8,10,16,17], while the total weak Roman domination number was recently introduced in [12].

A dominating set of cardinality $\gamma \left(G\right)$ will be called a $\gamma \left(G\right)$-set. A similar agreement will be assumed when referring to optimal sets associated with other parameters used in the article. As usual, we will use the acronyms TDS and STDS to refer to total dominating sets and secure total dominating sets, respectively.

A TDS X is said to be a total outer-connected dominating set if the subgraph induced by $V\left(G\right)\backslash X$ is connected. The total outer-connected domination number of G, denoted by ${\gamma }_{toc}\left(G\right)$, is the minimum cardinality among all total outer-connected dominating sets of G. This parameter was introduced by Cyman in [18] and studied further in [19,20,21].

An independent set of a graph G is a subset of vertices such that no two vertices in the subset represent an edge of G. The maximum cardinality among all independent sets is the independence number of G, denoted by $\alpha \left(G\right)$. Analogously, two edges in a graph G are independent if they are not adjacent in G. A set of pairwise independent edges of G is called a matching of G. The matching number ${\alpha }^{\prime }\left(G\right)$ , sometimes known as the edge independence number, is the maximum cardinality among all matchings of G.

For the remainder of the paper, definitions will be introduced whenever a concept is needed.

3. Secure Total Domination & Independence

Klostermeyer and Mynhardt [9] in 2008, established the following upper bound.

Theorem 1.

[9] For any graph G with no isolated vertex,

$${\gamma }_{st}\left(G\right)\le 3\alpha \left(G\right)-1.$$

In 2017 Duginov [14] answered the following open question posed by Klostermeyer and Mynhardt [9] p. 282: Is there a graph G such that ${\gamma }_{st}\left(G\right)=3\alpha \left(G\right)-1$, where $\alpha \left(G\right)\ge 2$? Duginov provided a negative answer to this question by confirming the suspicions of Klostermeyer and Mynhardt that ${\gamma }_{st}\left(G\right)\le 2\alpha \left(G\right).$

Theorem 2.

[14] For any graph G with no isolated vertex,

$${\gamma }_{st}\left(G\right)\le 2\alpha \left(G\right).$$

We now proceed to improve the bound above.

Since $\gamma \left(G\right)\le \alpha \left(G\right)$, the following result improves Theorem 2.

Theorem 3.

For any graph G with no isolated vertex,

$${\gamma }_{st}\left(G\right)\le \alpha \left(G\right)+\gamma \left(G\right).$$

Proof. 

Let D be a $\gamma \left(G\right)$-set. Let I be an $\alpha \left(G\right)$-set such that $|D\cap I|$ is at its maximum among all $\alpha \left(G\right)$-sets. Notice that for any $x\in D\cap I$,

$$epn(x,D\cup I)\cup ipn(x,D\cup I)\subseteq epn(x,I).$$

(1)

We next define a set $S\subseteq V\left(G\right)$ of minimum cardinality among the sets satisfying the following properties.

(a)

$D\cup I\subseteq S$.

(b)

For every vertex $x\in D\cap I$,

(b1)

if $epn(x,D\cup I)\ne ⌀$, then $S\cap epn(x,D\cup I)\ne ⌀$;

(b2)

if $epn(x,D\cup I)=⌀$, $ipn(x,D\cup I)\ne ⌀$ and $epn(x,I)\backslash ipn(x,D\cup I)\ne ⌀$, then either $epn(x,I)\backslash D=⌀$ or $S\cap epn(x,I)\backslash D\ne ⌀$;

(b3)

if $epn(x,D\cup I)=⌀$ and $epn(x,I)=ipn(x,D\cup I)\ne ⌀$, then $S\cap N\left(epn\right(x,I\left)\right)\backslash \left\{x\right\}\ne ⌀$;

(b4)

if $epn(x,D\cup I)=ipn(x,D\cup I)=⌀$, then $N\left(x\right)\backslash (D\cup I)=⌀$ or $S\cap N\left(x\right)\backslash (D\cup I)\ne ⌀$.

Since D and I are dominating sets, from (a) and (b) we conclude that S is a TDS. From now on, let $v\in V\left(G\right)\backslash S$. Observe that there exists a vertex $u\in N\left(v\right)\cap I\subseteq N\left(v\right)\cap S$, as $I\subseteq S$ is an $\alpha \left(G\right)$-set. To conclude that S is a STDS, we only need to prove that $S^{\prime }=(S\backslash \left\{u\right\})\cup \left\{v\right\}$ is a TDS of G.

First, notice that every vertex in $V\left(G\right)\backslash N\left(u\right)$ is dominated by some vertex in $S^{\prime }$, because S is a TDS of G. Let $w\in N\left(u\right)$. Now, we differentiate two cases with respect to vertex u.

• Case 1. $u\in I\backslash D$. If $w\notin D$, then there exists some vertex in $D\subseteq S^{\prime }$ which dominates w, as D is a dominating set. Suppose that $w\in D$. If $w\in ipn(u,D\cup I)$, then $I^{\prime }=(I\cup \left\{w\right\})\backslash \left\{u\right\}$ is an $\alpha \left(G\right)$-set such that $|D\cap I^{\prime }|>|D\cap I|$, which is a contradiction. Hence, $w\notin ipn(u,D\cup I)$, which implies that there exists some vertex in $(D\cup I)\backslash \left\{u\right\}\subseteq S^{\prime }$ which dominates w.
• Case 2. $u\in I\cap D$. We first suppose that $w\notin D$. If $w\notin epn(u,D\cup I)$, then w is dominated by some vertex in $(D\cup I)\backslash \left\{u\right\}\subseteq S^{\prime }$. If $w\in epn(u,D\cup I)$, then by $\left(\mathrm{b}1\right)$ and the fact that in this case all vertices in $epn(u,D\cup I)$ form a clique, w is dominated by some vertex in $S\backslash \left\{u\right\}\subseteq S^{\prime }$. From now on, suppose that $w\in D$. If $w\notin ipn(u,D\cup I)$, then there exists some vertex in $(D\cup I)\backslash \left\{u\right\}\subseteq S^{\prime }$ which dominates w. Finally, we consider the case in that $w\in ipn(u,D\cup I)$.

We claim that $ipn(u,D\cup I)=\left\{w\right\}$. In order to prove this claim, suppose that there exists $w^{\prime }\in ipn(u,D\cup I)\backslash \left\{w\right\}$. Notice that $w^{\prime }\in D$. By (1) and the fact that all vertices in $epn(u,I)$ form a clique, we prove that $w{w}^{\prime }\in E\left(G\right)$, and so $w\notin ipn(u,D\cup I)$, which is a contradiction. Therefore, $ipn(u,D\cup I)=\left\{w\right\}$ and, as a result,

$$epn(u,D\cup I)\cup \left\{w\right\}\subseteq epn(u,I).$$

(2)

In order to conclude the proof, we consider the following subcases.

Subcase 2.1. $epn(u,D\cup I)\ne ⌀$. By (2), $\left(\mathrm{b}1\right)$, and the fact that all vertices in $epn(u,I)$ form a clique, we conclude that w is adjacent to some vertex in $S\backslash \left\{u\right\}\subseteq S^{\prime }$, as desired.

Subcase 2.2. $epn(u,D\cup I)=⌀$ and $epn(u,I)\backslash \left\{w\right\}\ne ⌀$. By (2), $\left(\mathrm{b}2\right)$, and the fact that all vertices in $epn(u,I)$ form a clique, we show that w is dominated by some vertex in $S\backslash \left\{u\right\}\subseteq S^{\prime }$, as desired.

Subcase 2.3. $epn(u,D\cup I)=⌀$ and $epn(u,I)=\left\{w\right\}$. In this case, by $\left(\mathrm{b}3\right)$ we deduce that w is dominated by some vertex in $S\backslash \left\{u\right\}\subseteq S^{\prime }$, as desired.

According to the two cases above, we can conclude that $S^{\prime }$ is a TDS of G, and so S is a STDS of G. Now, by the the minimality of $\left|S\right|$, we show that $\left|S\right|\le |D\cup I|+|D\cap I|=\left|D\right|+\left|I\right|$. Therefore, ${\gamma }_{st}\left(G\right)\le \left|S\right|\le \left|I\right|+\left|D\right|=\alpha \left(G\right)+\gamma \left(G\right)$, which completes the proof. □

The bound above is tight. For instance, it is achieved for any corona product graph $G=H_1\odot H_2$, where $H_1$ is an arbitrary graph and $H_2$ is the disjoint union of k complete nontrivial graphs. Notice that $\alpha \left(G\right)=k|V\left(H_1\right)|$, $\gamma \left(G\right)=|V\left(H_1\right)|$ and ${\gamma }_{st}\left(G\right)=(k+1)\left|V\left(H_1\right)\right|=\alpha \left(G\right)+\gamma \left(G\right)$. Another example is the graph G shown in Figure 2, where ${\gamma }_{st}\left(G\right)=8$, $\alpha \left(G\right)=6$ and $\gamma \left(G\right)=2$.

4. Secure Total Domination & Other Kinds of Domination

For any graph G with no isolated vertex, $V\left(G\right)$ is a secure total dominating set, which implies that ${\gamma }_{st}\left(G\right)\le \left|V\left(G\right)\right|$. All graphs achieving this trivial bound were characterized by Benecke et al. as follows.

Theorem 4.

[11] Let G be a graph of order n. Then ${\gamma }_{st}\left(G\right)=n$ if and only if $V\left(G\right)\backslash \left(L\right(G)\cup S(G\left)\right)$ is an independent set.

Since every secure total dominating set is a total dominating set, it is clear that ${\gamma }_t\left(G\right)\le {\gamma }_{st}\left(G\right)$. All graphs satisfying the equality were characterized by Klostermeyer and Mynhardt in [9].

Theorem 5.

[9] If G is a connected graph, then the following statements are equivalent.

• ${\gamma }_{st}\left(G\right)={\gamma }_t\left(G\right)$.
• ${\gamma }_{st}\left(G\right)=2$.
• G has two universal vertices.

The result above is an important tool to characterize all graphs with ${\gamma }_{st}\left(G\right)=3$. To begin with, we need to state the following basic tool.

Proposition 1.

If H is a spanning subgraph (with no isolated vertex) of a graph G, then

$${\gamma }_{st}\left(G\right)\le {\gamma }_{st}\left(H\right).$$

Proof. 

Let $E^{-}=\{e_1,\dots ,e_k\}$ be the set of all edges of G not belonging to the edge set of H. Let $H_0=G$ and, for every $i\in \{1,\dots ,k\}$, let $X_i=\{e_1,\dots ,e_i\}$ and $H_i=G-X_i$. Since any STDS of $H_i$ is a STDS of $H_{i-1}$, we can conclude that ${\gamma }_{st}\left(H_{i-1}\right)\le {\gamma }_{st}\left(H_i\right)$. Hence, ${\gamma }_{st}\left(G\right)={\gamma }_{st}\left(H_0\right)\le {\gamma }_{st}\left(H_1\right)\le \cdots \le {\gamma }_{st}\left(H_k\right)={\gamma }_{st}\left(H\right)$. □

Let $\mathcal{G}$ be the family of graphs H of order $n\ge 3$ such that the subgraph induced by three vertices of H contains a path $P_3$ and the remaining $n-3$ vertices have degree two and they form an independent set. Figure 1 shows a graph belonging to $\mathcal{G}$.

Theorem 6.

Given a graph G, the following statements are equivalent.

• ${\gamma }_{st}\left(G\right)=3$.
• G has at most one universal vertex and there exists $H\in \mathcal{G}$ which is a spanning subgraph of G.

Proof. 

Let D be a ${\gamma }_{st}\left(G\right)$-set and assume that $\left|D\right|=3$. By Theorem 5, G has at most one universal vertex. Let $D=\{u,v,w\}$ and notice that $\langle D\rangle$ contains a path $P_3$, as D is a total dominating set of G. Since D is a STDS of G, we observe that $\left|N\right(z)\cap D|\ge 2$ for every $z\in V\left(G\right)\backslash D$. Hence, in this case, G contains a spanning subgraph belonging to $\mathcal{G}$.

Conversely, since G has at most one universal vertex, by Theorem 5 we have that ${\gamma }_{st}\left(G\right)\ge 3$. Moreover, it is readily seen that ${\gamma }_{st}\left(H\right)\le 3$ for any $H\in \mathcal{G}$. Hence, if $H\in \mathcal{G}$ is a spanning subgraph of G, by Proposition 1 it follows that ${\gamma }_{st}\left(G\right)\le 3$. Therefore, ${\gamma }_{st}\left(G\right)=3$. □

We now consider the relationship between ${\gamma }_s\left(G\right)$ and ${\gamma }_{st}\left(G\right)$.

Theorem 7.

[9] Let G be a graph with no isolated vertex.

(i) 

If $\delta \left(G\right)=1$, then ${\gamma }_s\left(G\right)+1\le {\gamma }_{st}\left(G\right)$.

(ii) 

If $\delta \left(G\right)\ge 2$, then ${\gamma }_s\left(G\right)\le {\gamma }_{st}\left(G\right)\le 2{\gamma }_s\left(G\right)$.

A natural question is if the bound ${\gamma }_{st}\left(G\right)\le 2{\gamma }_s\left(G\right)$, due to Klostermeyer and Mynhardt, can be improved with ${\gamma }_{st}\left(G\right)\le {\gamma }_s\left(G\right)+\gamma \left(G\right)$. The example given in Figure 2 shows that, in general, this inequality does not hold.

In Theorem 10 we will show some cases in which ${\gamma }_{st}\left(G\right)\le {\gamma }_s\left(G\right)+\gamma \left(G\right)$. To this end, we need to outline the following two known results.

Theorem 8.

[12] The following inequalities hold for any graph G with no isolated vertex.

(i) 

${\gamma }_t\left(G\right)\le {\gamma }_{tr}\left(G\right)\le {\gamma }_{st}\left(G\right)$.

(ii) 

${\gamma }_{tr}\left(G\right)\le min\{{\gamma }_t\left(G\right),{\gamma }_r\left(G\right)\}+\gamma \left(G\right)$.

Although the problem of characterizing all graphs with ${\gamma }_{tr}\left(G\right)={\gamma }_{st}\left(G\right)$ remains open, some particular cases were described in [12].

Theorem 9.

[12]

(i) 

${\gamma }_{st}\left(G\right)=\gamma \left(G\right)+1$ if and only if ${\gamma }_{tr}\left(G\right)=\gamma \left(G\right)+1$.

(ii) 

For any $\{K_{1,3},K_{1,3}+e\}$-free graph G with no isolated vertex, ${\gamma }_{st}\left(G\right)={\gamma }_{tr}\left(G\right).$

(iii) 

For any graph G with no isolated vertex and maximum degree $\Delta \left(G\right)\le 2$, ${\gamma }_{st}\left(G\right)={\gamma }_{tr}\left(G\right).$

From Theorems 8 and 9 (ii), and using the fact that ${\gamma }_r\left(G\right)\le {\gamma }_s\left(G\right)$, we can show that the bound ${\gamma }_{st}\left(G\right)\le 2{\gamma }_s\left(G\right)$ established in Theorem 7 can be improved for any $\{K_{1,3},K_{1,3}+e\}$-free graph.

Theorem 10.

For any $\{K_{1,3},K_{1,3}+e\}$-free graph G with no isolated vertex,

$${\gamma }_{st}\left(G\right)\le min\{{\gamma }_t\left(G\right),{\gamma }_r\left(G\right)\}+\gamma \left(G\right)\le {\gamma }_s\left(G\right)+\gamma \left(G\right).$$

The previous bounds are tight. They are achieved, for instance, for the wheel graph $G\cong N_1+C_4$ and for $G\cong N_2+P_3$, which is the join of $N_2$ and $P_3$. For these two graphs we have that ${\gamma }_{st}\left(G\right)=3$, ${\gamma }_s\left(G\right)={\gamma }_r\left(G\right)={\gamma }_t\left(G\right)=2$ and $\gamma \left(G\right)=1$.

To derive a consequence of Theorem 10 we need to state the following result due to Burger et al. [6].

Theorem 11.

[6] For any connected graph $G\ncong C_5$ of order n and $\delta \left(G\right)\ge 2$,

$${\displaystyle {\gamma }_s\left(G\right)\le ⌊\frac{n}{2}⌋.}$$

Notice that ${\gamma }_{st}\left(C_5\right)=4=⌊\frac{5}{2}⌋+\gamma \left(C_5\right)$. Hence, from Theorems 10 and 11 we immediately have the next result.

Theorem 12.

For any connected $\{K_{1,3},K_{1,3}+e\}$-free graph G of order n and $\delta \left(G\right)\ge 2$,

$${\displaystyle {\gamma }_{st}\left(G\right)\le ⌊\frac{n}{2}⌋+\gamma \left(G\right).}$$

The bound above is tight. It is achieved for $G\cong N_1+C_4$, $G\cong C_5$ and $G\cong C_6$, where ${\gamma }_{st}\left(G\right)$ equals $3,4$ and 5, respectively.

The following result shows us a relationship between the secure total domination number and the total outer-connected domination number.

Theorem 13.

Let G be a graph of order n. If ${\gamma }_{toc}\left(G\right)\le n-2$, then

$${\gamma }_{st}\left(G\right)\le ⌊\frac{{\gamma }_{toc}\left(G\right)+n}{2}⌋.$$

Proof. 

We assume that ${\gamma }_{toc}\left(G\right)\le n-2$. Let D be a ${\gamma }_{toc}\left(G\right)$-set and S a $\gamma (\langle V(G)\backslash D\rangle )$-set. Since D is a TDS of G, $D\cup S$ is a TDS as well. Furthermore, every vertex $u\in V\left(G\right)\backslash (D\cup S)$ is dominated by some vertex $v\in S$, and $D\subseteq (D\cup S\cup \{u\left\}\right)\backslash \left\{v\right\}$ is a TDS of G. Hence, $D\cup S$ is a STDS of G, which implies that ${\gamma }_{st}\left(G\right)\le |D\cup S|=\left|D\right|+\left|S\right|$. Now, since $\langle V\left(G\right)\backslash D\rangle$ is a connected nontrivial graph, we have that $\left|S\right|=\gamma \left(\langle V\left(G\right)\backslash D\rangle \right)\le \frac{\left|V\right(G)\backslash D|}{2}=\frac{n-{\gamma }_{toc}\left(G\right)}{2}$. Therefore, ${\gamma }_{st}\left(G\right)\le \lfloor \frac{{\gamma }_{toc}\left(G\right)+n}{2}\rfloor$, which completes the proof. □

The bound above is tight. For instance, it is achieved for the wheel graph $G\cong N_1+C_4$ and for $G\cong N_2+P_3$. In both cases ${\gamma }_{st}\left(G\right)=3$ and ${\gamma }_{toc}\left(G\right)=2$.

The following result was obtained by Favaron et al. in [20].

Theorem 14.

[20] For any graph G of order n, diameter $diam\left(G\right)\le 2$ and minimum degree $\delta \left(G\right)\ge 3$,

$${\gamma }_{toc}\left(G\right)\le ⌊\frac{2n-2}{3}⌋.$$

The following result is a direct consequence of combining the result above and Theorem 13.

Theorem 15.

For any graph G of order n, diameter two and minimum degree $\delta \left(G\right)\ge 3$,

$${\gamma }_{st}\left(G\right)\le ⌊\frac{5n-2}{6}⌋.$$

The bound above is achieved for the wheel graph $G\cong N_1+C_4$ and for $G\cong N_2+P_3$. As we already know, in both cases ${\gamma }_{st}\left(G\right)=3$.

5. Secure Total Domination & Matching

To begin this section, we proceed to introduce new definitions and terminology. Given a matching $\mathcal{M}$ of a graph G, let $V_{\mathcal{M}}$ be the set formed by the end-vertices of edges belonging to $\mathcal{M}$. Given a vertex $v\in V_{\mathcal{M}}$, we say that $v^{\prime }\in V_{\mathcal{M}}$ is the partner of v if $v{v}^{\prime }\in \mathcal{M}$. Observe that if $v^{\prime }$ is the partner of v, then v is the partner of $v^{\prime }$.

A maximum matching is a matching of cardinality ${\alpha }^{\prime }\left(G\right)$. The following lemmas show some properties of maximum matchings.

Lemma 1.

Let $\mathcal{M}$ be a maximum matching of a graph G. The following statements hold.

(i) 

$N\left(u\right)\subseteq V_{\mathcal{M}}$ for every $u\in V\left(G\right)\backslash V_{\mathcal{M}}$.

(ii) 

If $u\in V\left(G\right)\backslash V_{\mathcal{M}}$ is adjacent to $v\in V_{\mathcal{M}}$, then $N\left(v^{\prime }\right)\subseteq V_{\mathcal{M}}\cup \left\{u\right\}$, where $v^{\prime }$ is the partner of v.

Proof. 

Let $u\in V\left(G\right)\backslash V_{\mathcal{M}}$. If there exists a vertex $w\in N\left(u\right)\cap (V\left(G\right)\backslash V_{\mathcal{M}})$, then the set $\mathcal{M}\cup \left\{uw\right\}$ is a matching of G of cardinality greater than $\left|\mathcal{M}\right|$, which is a contradiction. Hence, $N\left(u\right)\subseteq V_{\mathcal{M}}$ and (i) follows.

Now, we suppose that there exists $u\in V\left(G\right)\backslash V_{\mathcal{M}}$ and a vertex $v\in N\left(u\right)\cap V_{\mathcal{M}}$. Let $v^{\prime }$ be the partner of v. If there exists a vertex $w\in N\left(v^{\prime }\right)\cap (V\left(G\right)\backslash (V_{\mathcal{M}}\cup \left\{u\right\}))$, then the set $\mathcal{M}\backslash \left\{v{v}^{\prime }\right\}\cup \{uv,v^{\prime }w\}$ is a matching of G of cardinality greater than $\left|\mathcal{M}\right|$, which is a contradiction. Hence, $N\left(v^{\prime }\right)\subseteq V_{\mathcal{M}}\cup \left\{u\right\}$ and (ii) follows. □

Lemma 2.

For any graph G with $L\left(G\right)\ne \varnothing$, there exists a maximum matching $\mathcal{M}$ such that for each vertex $x\in S\left(G\right)$ there exists $y\in L\left(G\right)$ such that $xy\in \mathcal{M}$.

Proof. 

Let $\mathcal{M}$ be a maximum matching of G such that $|V_{\mathcal{M}}\cap L\left(G\right)|$ is maximum. It is easy to see that the maximality of $\mathcal{M}$ leads to $S\left(G\right)\subseteq V_{\mathcal{M}}$. Suppose that there exists a support vertex x such that $x{x}^{\prime }\in \mathcal{M}$ and $x^{\prime }\notin L\left(G\right)$. Let $y\in N\left(x\right)\cap L\left(G\right)$. Notice that the set ${\mathcal{M}}^{\prime }=\mathcal{M}\backslash \left\{x{x}^{\prime }\right\}\cup \left\{xy\right\}$ is a maximum matching of G and $|V_{{\mathcal{M}}^{\prime }}\cap L\left(G\right)|>|V_{\mathcal{M}}\cap L\left(G\right)|$, which is a contradiction. Therefore, the result follows. □

The next result provides a relationship between the secure total domination number, the matching number and some special vertices of a graph.

Theorem 16.

For any graph G with minimum degree $\delta \left(G\right)=1$,

$${\gamma }_{st}\left(G\right)\le 2{\alpha }^{\prime }\left(G\right)+\left|L\left(G\right)\right|-\left|S\left(G\right)\right|+|I_G|.$$

Proof. 

Let $\mathcal{M}$ be a maximum matching satisfying Lemma 2. Let $S=V_{\mathcal{M}}\cup L\left(G\right)\cup I_G$. Notice that $V_{\mathcal{M}}\cap I_G=\varnothing$ and $S\left(G\right)\subseteq V_{\mathcal{M}}$. Hence, $\left|S\right|=2{\alpha }^{\prime }\left(G\right)+\left|L\left(G\right)\right|-\left|S\left(G\right)\right|+|I_G|$.

Notice that that S is a TDS of G. We shall show that S is a STDS of G. Now, let $v\in V\left(G\right)\backslash S$. Since $v\notin I_G$ and $V_{\mathcal{M}}$ is a dominating set of G, there exists a vertex $u\in V_{\mathcal{M}}\backslash S\left(G\right)$ which is adjacent to v. Let $S^{\prime }=(S\backslash \left\{u\right\})\cup \left\{v\right\}$. We will see that $S^{\prime }$ is a TDS of G as well. Since S is a TDS of G, every vertex $w\in V\left(G\right)\backslash N\left(u\right)$ is adjacent to some vertex belonging to $S^{\prime }$. Let $w\in N\left(u\right)$ and observe that $\left|N\right(w\left)\right|\ge 2$ as $u\notin S\left(G\right)$.

If $w\in V\left(G\right)\backslash V_{\mathcal{M}}$, then by Lemma 1 (i) we have that $N\left(w\right)\subseteq V_{\mathcal{M}}$. Hence there exists a vertex in $V_{\mathcal{M}}\backslash \left\{u\right\}\subseteq S^{\prime }$ which is adjacent to w, as $\left|N\right(w\left)\right|\ge 2$. Now, if $w\in V_{\mathcal{M}}\backslash \left\{u^{\prime }\right\}$, where $u^{\prime }$ is the partner of u, then w is adjacent to its partner, which belongs to $S^{\prime }$. Finally, if $w=u^{\prime }$, then by Lemma 1 (ii) we have that $N\left(w\right)\subseteq V_{\mathcal{M}}\cup \left\{v\right\}$ and since $\left|N\right(w\left)\right|\ge 2$ it follows that $N\left(w\right)\subseteq (V_{\mathcal{M}}\backslash \left\{u\right\})\cup \left\{v\right\}\subseteq S^{\prime }$.

Thus, $S^{\prime }$ is a TDS of G, as desired. Therefore, S is a STDS and so ${\gamma }_{st}\left(G\right)\le \left|S\right|=2{\alpha }^{\prime }\left(G\right)+\left|L\left(G\right)\right|-\left|S\left(G\right)\right|+|I_G|$. □

The bound above is tight. For instance, it is achieved for the graph shown in Figure 3. In this case, ${\gamma }_{st}\left(G\right)=22$, ${\alpha }^{\prime }\left(G\right)=7$, $\left|L\right(G\left)\right|=12$, $\left|S\right(G\left)\right|=6$ and $|I_G|=2$.

From now on we consider the case of graphs with minimum degree $\delta \left(G\right)\ge 2$.

Definition 1.

Given a maximum matching $\mathcal{M}$ of a graph G with $\delta \left(G\right)\ge 2$, we construct a set $D_{\mathcal{M}}\subseteq V_{\mathcal{M}}$ as follows.

(i) 

$|D_{\mathcal{M}}|={\alpha }^{\prime }\left(G\right)$.

(ii) 

$xy\notin \mathcal{M}$ for all $x,y\in D_{\mathcal{M}}$.

(iii) 

$|N\left(x\right)\cap (V\left(G\right)\backslash V_{\mathcal{M}})|\ge |N\left(x^{\prime }\right)\cap (V\left(G\right)\backslash V_{\mathcal{M}})|$ for all $x\in D_{\mathcal{M}}$, where $x^{\prime }$ is the partner of x.

We proceed to show some properties of $D_{\mathcal{M}}\subseteq V_{\mathcal{M}}$.

Lemma 3.

Let $\mathcal{M}$ be a maximum matching of a graph G with $\delta \left(G\right)\ge 2$. The following statements hold.

(a) 

If $u\in V\left(G\right)\backslash V_{\mathcal{M}}$ is adjacent to $v^{\prime }\in V_{\mathcal{M}}\backslash D_{\mathcal{M}}$, then u is adjacent to $v\in D_{\mathcal{M}}$, where v is the partner of $v^{\prime }$.

(b) 

$D_{\mathcal{M}}$ is a dominating set of G.

(c) 

If $v\in D_{\mathcal{M}}$, then its partner $v^{\prime }\in V_{\mathcal{M}}\backslash D_{\mathcal{M}}$ satisfies that $|N\left(v^{\prime }\right)\cap V_{\mathcal{M}}|\ge \delta \left(G\right)-1$.

Proof. 

Let $u\in V\left(G\right)\backslash V_{\mathcal{M}}$. By Lemma 1 (i) we have that $N\left(u\right)\subseteq V_{\mathcal{M}}$. If there exists a vertex $v^{\prime }\in V_{\mathcal{M}}\backslash D_{\mathcal{M}}$, then by Lemma 1 (ii) we have that $N\left(v\right)\subseteq V_{\mathcal{M}}\cup \left\{u\right\}$ (where $v\in D_{\mathcal{M}}$ is the partner of $v^{\prime }$). By item (iii) in the definition of $D_{\mathcal{M}}$ it follows that $u\in N\left(v\right)$ and (a) holds.

From item (a) we deduce that $N\left(u\right)\cap D_{\mathcal{M}}\ne \varnothing$. Now, by definition of $D_{\mathcal{M}}$, every vertex in $V_{\mathcal{M}}\backslash D_{\mathcal{M}}$ is dominated by its partner, which belongs to $D_{\mathcal{M}}$. Therefore, $D_{\mathcal{M}}$ is a dominating set of G and so (b) follows.

Now, let $z\in D_{\mathcal{M}}$ and $z^{\prime }$ its partner. If $|N\left(z^{\prime }\right)\cap V_{\mathcal{M}}|\le \delta \left(G\right)-2$, then there exist two vertices $x,y\in N\left(z^{\prime }\right)\cap (V\left(G\right)\backslash V_{\mathcal{M}})$. By Lemma 3 (a) we have that $x,y\in N\left(z\right)$, which is a contradiction by Lemma 1 (ii). Therefore, $|N\left(z^{\prime }\right)\cap V_{\mathcal{M}}|\ge \delta \left(G\right)-1$ and (c) follows, which completes the proof. □

Theorem 17.

For any graph G with minimum degree $\delta \left(G\right)\ge 2$,

$${\gamma }_{st}\left(G\right)\le 2{\alpha }^{\prime }\left(G\right)-\delta \left(G\right)+2.$$

Proof. 

Let n be the order of G. Let $v\in V\left(G\right)$ be a vertex of degree $\delta \left(G\right)$ and $u\in N\left(v\right)$. It is readily seen that the set $S=\left(V\right(G)\backslash N(v\left)\right)\cup \left\{u\right\}$ is a STDS of G and, as a consequence, ${\gamma }_{st}\left(G\right)\le n-\delta \left(G\right)+1$. Thus, the inequality holds for $2{\alpha }^{\prime }\left(G\right)\in \{n-1,n\}$.

From now on we suppose that $2{\alpha }^{\prime }\left(G\right)\le n-2$. Let $\mathcal{M}$ be a maximum matching of G. Since $|V_{\mathcal{M}}|=2{\alpha }^{\prime }\left(G\right)\le n-2$, there exist two vertices $x,y\in V\left(G\right)\backslash V_{\mathcal{M}}$. By Lemma 3 (b) we have that $D_{\mathcal{M}}$ is a dominating set of G, which implies that there exists a vertex $v_x\in N\left(x\right)\cap D_{\mathcal{M}}$. Since $\delta \left(G\right)\ge 2$, by Lemmas 1 and 3 (a), there exists a vertex $v_y\in N\left(y\right)\cap (D_{\mathcal{M}}\backslash \left\{v_x\right\})$ and also we deduce that $N\left(x\right)\cup N\left(y\right)\subseteq V_{\mathcal{M}}$ and $N\left(x\right)\cap N\left(y\right)\subseteq D_{\mathcal{M}}$. Let $R=(N\left(x\right)\cup N\left(y\right))\cap D_{\mathcal{M}}$. Hence $\left|R\right|=|N\left(x\right)\cap N\left(y\right)|+|(N\left(x\right)\backslash N\left(y\right))\cap D_{\mathcal{M}}|+|(N\left(y\right)\backslash N\left(x\right))\cap D_{\mathcal{M}}|\ge (\left|N\left(x\right)\right|+\left|N\left(y\right)\right|)/2\ge \delta \left(G\right)$. Let $Z\subseteq R\backslash \{v_x,v_y\}$ such that $\left|Z\right|=\delta \left(G\right)-2$ and let $Z^{\prime }$ be the set of partners of the vertices in Z.

Let ${\mathcal{M}}^{\prime }=(\mathcal{M}\backslash \{v_x{v}_x^{\prime },v_y{v}_y^{\prime }\})\cup \{x{v}_x,y{v}_y\}$, where $v_x^{\prime }$ and $v_y^{\prime }$ are the partners of $v_x$ and $v_y$ respectively. Notice that ${\mathcal{M}}^{\prime }$ is a maximum matching of G and the set $D_{\mathcal{M}}^{\prime }=D_{\mathcal{M}}\subseteq V_{{\mathcal{M}}^{\prime }}$ satisfies the conditions given in Definition 1.

We will prove that $S=V_{{\mathcal{M}}^{\prime }}\backslash Z^{\prime }$ is a STDS of G. By Lemma 3 (b) we have that $D_{\mathcal{M}}$ is a dominating set of G, which implies that every vertex in $V\left(G\right)\backslash S$ is dominated by some vertex in $D_{\mathcal{M}}\subseteq S$. Also, every vertex in Z is dominated by either x or y, which belong to S, and every vertex in $S\backslash Z$ satisfies that its partner belongs to S as well. Hence S is a TDS of G.

Let $v\in V\left(G\right)\backslash S$ and let $S^{\prime }=(S\backslash \left\{v^{*}\right\})\cup \left\{v\right\}$, where either $v^{*}=v^{\prime }$ is the partner of v if $v\in Z^{\prime }$, or $v^{*}$ is a vertex belonging to $N\left(v\right)\cap D_{\mathcal{M}}$ if $v\in V\left(G\right)\backslash V_{{\mathcal{M}}^{\prime }}$ (notice that in this case, $v^{*}$ exists since $D_{\mathcal{M}}$ is a dominating set). We only need to prove that $S^{\prime }$ is a TDS of G. Since S is a TDS of G, every vertex in $V\left(G\right)\backslash N\left(v^{*}\right)$ has at least one neighbour in $S^{\prime }$. Now, let $u\in N\left(v^{*}\right)$ and consider the following two cases.

Case 1. $u\in V\left(G\right)\backslash V_{{\mathcal{M}}^{\prime }}$. Since $|V_{{\mathcal{M}}^{\prime }}\cap (V\left(G\right)\backslash S^{\prime })|=\delta \left(G\right)-1$, by Lemma 1 (i) we deduce that there exists some vertex in $N\left(u\right)\cap S^{\prime }$.

Case 2. $u\in V_{{\mathcal{M}}^{\prime }}$. In this case, we analyse three subcases. If $u\in Z$, then u is dominated by either x or y, which belong to $S^{\prime }$. If $u=v$, then as $u\in V_{{\mathcal{M}}^{\prime }}\backslash D_{\mathcal{M}}^{\prime }$, by Lemma 3 (c) it follows that $|N\left(u\right)\cap V_{{\mathcal{M}}^{\prime }}|\ge \delta \left(G\right)-1$. As in this case $|V_{{\mathcal{M}}^{\prime }}\cap (V\left(G\right)\backslash S^{\prime })|=\delta \left(G\right)-2$, we deduce that $N\left(u\right)\cap S^{\prime }\ne \varnothing$. Finally, if $u\in V_{{\mathcal{M}}^{\prime }}\backslash (Z\cup \left\{v\right\})$, then its partner belongs to $S^{\prime }$.

Hence, $S^{\prime }$ is a TDS of G, as desired. Therefore, S is a STDS of G and ${\gamma }_{st}\left(G\right)\le \left|S\right|=|V_{{\mathcal{M}}^{\prime }}\backslash Z^{\prime }|=2{\alpha }^{\prime }\left(G\right)-\delta \left(G\right)+2$, which completes the proof. □

The bound above is tight. For instance, it is achieved for the graphs $G\cong N_2+P_3$ and $G\cong N_1+C_4$. In both cases ${\gamma }_{st}\left(G\right)=3$, ${\alpha }^{\prime }\left(G\right)=2$ and $\delta \left(G\right)=3$.

Cockayne et al. in [8] obtained the following bound on the secure domination number in terms of the order and the matching number.

Theorem 18.

[8] If a graph G of order n does not have isolated vertices, then

$${\gamma }_s\left(G\right)\le n-{\alpha }^{\prime }\left(G\right).$$

Therefore, by Theorems 10 and 18 we deduce the following result.

Theorem 19.

For any $\{K_{1,3},K_{1,3}+e\}$-free graph G with minimum degree $\delta \left(G\right)\ge 1$ and order n,

$${\gamma }_{st}\left(G\right)\le n-{\alpha }^{\prime }\left(G\right)+\gamma \left(G\right).$$

The bound above is tight. For instance, it is achieved for the graphs $G\cong C_6$ and $G\cong P_6$, as for these graphs we have ${\gamma }_{st}\left(G\right)=5$, ${\alpha }^{\prime }\left(G\right)=3$ and $\gamma \left(G\right)=2$.

The k-domination number of G, denoted by ${\gamma }_k\left(G\right)$, is another well-known parameter [3]. The following theorem is a contribution of DeLaViña et al. in [22].

Theorem 20.

[22] Let k be a positive integer. For any graph G with minimum degree $\delta \left(G\right)\ge 2k-1$,

$${\gamma }_k\left(G\right)\le {\alpha }^{\prime }\left(G\right).$$

Since every ${\gamma }_2\left(G\right)$-set is a secure dominating set of G, it is immediate that ${\gamma }_s\left(G\right)\le {\gamma }_2\left(G\right)$, and so Theorems 10 and 20 lead to the following result.

Theorem 21.

For any $\{K_{1,3},K_{1,3}+e\}$-free graph G with minimum degree $\delta \left(G\right)\ge 3$,

$${\gamma }_{st}\left(G\right)\le {\alpha }^{\prime }\left(G\right)+\gamma \left(G\right).$$

The bound above is tight. For instance, it is achieved for the wheel graph $G\cong N_1+C_4$ and for $G\cong N_2+P_3$, as in both cases ${\gamma }_{st}\left(G\right)=3$, ${\alpha }^{\prime }\left(G\right)=2$ and $\gamma \left(G\right)=1$.

6. Conclusions

This article is a contribution to the theory of protection of graphs. In particular, it is devoted to the study of the secure total domination number of a graph. We study the properties of this parameter in order to obtain its exact value or general bounds. Among our main contributions we highlight the following.

• We show that ${\gamma }_{st}\left(G\right)\le \alpha \left(G\right)+\gamma \left(G\right)$. Since $\gamma \left(G\right)\le \alpha \left(G\right)$, this result improves the bound ${\gamma }_{st}\left(G\right)\le 2\alpha \left(G\right)$ obtained in [14].
• We characterize the graphs with ${\gamma }_{st}\left(G\right)=3$.
• We show that if G is a $\{K_{1,3},K_{1,3}+e\}$-free graph G with no isolated vertex, then ${\gamma }_{st}\left(G\right)\le min\{{\gamma }_t\left(G\right),{\gamma }_r\left(G\right)\}+\gamma \left(G\right)\le {\gamma }_s\left(G\right)+\gamma \left(G\right).$
• We study the relationship that exists between the secure total domination number and the matching number of a graph. In particular, we obtain the following results.

  (a)

  ${\gamma }_{st}\left(G\right)\le 2{\alpha }^{\prime }\left(G\right)+\left|L\left(G\right)\right|-\left|S\left(G\right)\right|+|I_G|$ for any graph G of minimum degree one.

  (b)

  ${\gamma }_{st}\left(G\right)\le 2{\alpha }^{\prime }\left(G\right)-\delta \left(G\right)+2$ for every graph G of minimum degree $\delta \left(G\right)\ge 2$.

  (c)

  ${\gamma }_{st}\left(G\right)\le {\alpha }^{\prime }\left(G\right)+\gamma \left(G\right)$ for every $\{K_{1,3},K_{1,3}+e\}$-free graph G of minimum degree $\delta \left(G\right)\ge 3$.

All bounds obtained in the paper are tight.