## Trees with Large Neighborhood Total Domination Number

Michael A. Henning ∗ and Kirsti Wash †

Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa Email: mahenning@uj.ac.za Email: kirstiw@g.clemson.edu

## Abstract

In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam [Opuscula Math. 31 (2011), 519-531]. A neighborhood total dominating set, abbreviated NTD-set, in a graph G is a dominating set S in G with the property that the subgraph induced by the open neighborhood of the set S has no isolated vertex. The neighborhood total domination number, denoted by γ nt ( G ), is the minimum cardinality of a NTD-set of G . Every total dominating set is a NTD-set, implying that γ G ( ) ≤ γ nt ( G ) ≤ γ t ( G ), where γ G ( ) and γ t ( G ) denote the domination and total domination numbers of G , respectively. Arumugam and Sivagnanam posed the problem of characterizing the connected graphs G of order n ≥ 3 achieving the largest possible neighborhood total domination number, namely γ nt ( G ) = /ceilingleft n/ 2 . /ceilingright A partial solution to this problem was presented by Henning and Rad [Discrete Applied Mathematics 161 (2013), 2460-2466] who showed that 5-cycles and subdivided stars are the only such graphs achieving equality in the bound when n is odd. In this paper, we characterize the extremal trees achieving equality in the bound when n is even. As a consequence of this tree characterization, a characterization of the connected graphs achieving equality in the bound when n is even can be obtained noting that every spanning tree of such a graph belongs to our family of extremal trees.

Keywords: Domination; Total domination; Neighborhood total domination.

AMS subject classification: 05C69

∗ Research supported in part by the South African National Research Foundation and the University of Johannesburg

† Research supported in part by the University of Johannesburg

## 1 Introduction

In this paper we continue the study of a parameter, called the neighborhood total domination number, that is squeezed between arguably the two most important domination parameters, namely the domination number and the total domination number. A dominating set in a graph G is a set S of vertices of G such that every vertex in V ( G ) \ S is adjacent to at least one vertex in S . The domination number of G , denoted by γ G ( ), is the minimum cardinality of a dominating set of G . A total dominating set , abbreviated a TD-set, of a graph G with no isolated vertex is a set S of vertices of G such that every vertex in V ( G ) is adjacent to at least one vertex in S . The total domination number of G , denoted by γ t ( G ), is the minimum cardinality of a TD-set of G . The literature on the subject of domination parameters in graphs up to the year 1997 has been surveyed and detailed in the two books [5, 6]. Total domination is now well studied in graph theory. For a recent book on the topic, see [10]. A survey of total domination in graphs can also be found in [7].

Arumugam and Sivagnanam [1] introduced and studied the concept of neighborhood total domination in graphs. A neighbor of a vertex v is a vertex different from v that is adjacent to v . The neighborhood of a set S is the set of all neighbors of vertices in S . A neighborhood total dominating set , abbreviated NTD-set, in a graph G is a dominating set S in G with the property that the subgraph induced by the open neighborhood of the set S has no isolated vertex. The neighborhood total domination number of G , denoted by γ nt ( G ), is the minimum cardinality of a NTD-set of G . A NTD-set of G of cardinality γ nt ( G ) is called a γ nt ( G )-set .

Every TD-set is a NTD-set, while every NTD-set is a dominating set. Hence the neighborhood total domination number is bounded below by the domination number and above by the total domination number as first observed by Arumugam and Sivagnanam in [1].

Observation 1 ([1, 8]) If G is a graph with no isolated vertex, then γ G ( ) ≤ γ nt ( G ) ≤ γ t ( G ) .

## 1.1 Terminology and Notation

For notation and graph theory terminology not defined herein, we refer the reader to [5]. Let G be a graph with vertex set V ( G ) of order n = | V ( G ) | and edge set E G ( ) of size m = | E G ( ) , | and let v be a vertex in V . We denote the degree of v in G by d G ( v ). The minimum degree among the vertices of G is denoted by δ G ( ). A vertex of degree one is called a leaf and its neighbor a support vertex . We denote the set of leaves in G by L G ( ), and the set of support vertices by S G ( ). A support vertex adjacent to two or more leaves is a strong support vertex . For a set S ⊆ V , the subgraph induced by S is denoted by G S [ ]. A 2packing in G is a set of vertices that are pairwise at distance at least 3 apart in G .

A cycle and path on n vertices are denoted by C n and P n , respectively. A star on n ≥ 2 vertices is a tree with a vertex of degree n -1 and is denoted by K 1 ,n -1 . A double star is a

tree containing exactly two vertices that are not leaves (which are necessarily adjacent). A subdivided star is a graph obtained from a star on at least two vertices by subdividing each edge exactly once. The subdivided star obtained from a star K 1 4 , , for example, is shown in Figure 1. We note that the smallest two subdivided stars are the paths P 3 and P 5 . Let F be the family of all subdivided stars. Let F ∈ F . If F = P 3 , we select a leaf of F and call it the link vertex of F , while if F = P 3 , the link vertex of F is the central vertex of F .

/negationslash

Figure 1: A subdivided star.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0109v1-figure-929511f9-9f9f-4316-b7b8-b81c754f70e2.jpg)

The open neighborhood of v is the set N G ( v ) = { u ∈ V | uv ∈ E } and the closed neighborhood of v is N G [ v ] = { v } ∪ N G ( v ). For a set S ⊆ V , its open neighborhood is the set N G ( S ) = ⋃ v ∈ S N G ( v ), and its closed neighborhood is the set N G [ S ] = N G ( S ) ∪ S . If the graph G is clear from the context, we simply write d( v ), N v ( ), N v [ ], N S ( ) and N S [ ] rather than d G ( v ), N G ( v ), N G [ v ], N G ( S ) and N G [ S ], respectively. As observed in [8] a NTD-set in G is a set S of vertices such that N S [ ] = V and G N S [ ( )] contains no isolated vertex.

/negationslash

A rooted tree distinguishes one vertex r called the root . For each vertex v = r of T , the parent of v is the neighbor of v on the unique ( r, v )-path, while a child of v is any other neighbor of v . A descendant of v is a vertex u such that the unique ( r, u )-path contains v . Let C v ( ) and D v ( ) denote the set of children and descendants, respectively, of v , and let D v [ ] = D v ( ) ∪ { v } . The maximal subtree at v is the subtree of T induced by D v [ ], and is denoted by T v .

## 2 Known Results

The following upper bound on the neighborhood total domination number of a connected graph in terms of its order is established in [8].

Theorem 2 ([8]) If G is a connected graph of order n ≥ 3 , then γ nt ( G ) ≤ ( n +1) 2 / .

In this paper we consider the following problem posed by Arumugam and Sivagnanam [1] to characterize the connected graphs of largest possible neighborhood total domination number.

Problem 1 ([1]) Characterize the connected graphs G of order n for which γ nt ( G ) = /ceilingleft n/ 2 /ceilingright .

A partial solution to this problem was presented by Henning and Rad [8] who provided the following characterization in the case when n is odd.

/negationslash

Theorem 3 ([8]) Let G = C 5 be a connected graph of order n ≥ 3 . If γ nt ( G ) = ( n +1) 2 / , then G ∈ F .

As first observed in [8], a characterization in the case when n is even and the minimum degree is at least 2 follows readily from a result on the restrained domination number of a graph due to Domke, Hattingh, Henning and Markus [4]. Let B , B , . . . , B 1 2 5 be the five graphs shown in Figure 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0109v1-figure-7acd80cc-ce8c-4f0b-8a0a-48fa89906f1b.jpg)

/negationslash

Theorem 4 ([8]) Let G = C 5 be a connected graph of order n ≥ 4 with δ G ( ) ≥ 2 . If γ nt ( G ) = n/ 2 , then G ∈ { B , B , B , B 1 2 3 4 , B 5 } .

## 3 The Family T of Trees

In this section we define a family of trees T as follows. Let T 0 be an arbitrary tree. Let T 1 be the tree obtained from T 0 by the following operation: for each vertex x ∈ V ( T 0 ), either add a new vertex and an edge joining it to x or add a new path P 3 and an edge joining its central vertex to x . Let T be the family of all trees T that can be obtained from T 1 by performing the following operation:

- · Choose a set of leaves, L 1 , in T 1 , that form a 2-packing (possibly L 1 = ∅ ). For each vertex v ∈ L 1 , add k ≥ 0 vertex-disjoint copies of P 2 and join v to exactly one end of each added copy of P 2 . We refer to these k added copies of P 2 as appended P 2 s associated with x .

Figure 3: A tree in the family T .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0109v1-figure-9a050774-2e46-4303-aadd-68a092aa39ec.jpg)

A tree in the family T is illustrated in Figure 3. For ease of reference, we introduce some terminology for a tree T ∈ T . We use the standard notation [ k ] = { 1 2 , , . . . , k } . First note that given a tree T ∈ T , a tree T 0 used to construct the tree T may not be unique. That

is, in some cases we may be able to choose two distinct trees T 0 and T ′ 0 such that T is obtained from either T 0 or T ′ 0 by performing different combinations of the above operations. Therefore, we refer to T 0 as an underlying tree of T , and we refer to T 1 as the corresponding base tree of T 0 .

The vertex set V ( T 1 ) of T 1 can be partitioned into sets V , . . . , V 1 /lscript such that each V i contains exactly one vertex of T 0 and T V [ i ] ∈ { P , K 2 1 3 , } for each i ∈ [ /lscript ]. We say that T V [ i ] is a P 2 -unit of T 1 if T V [ i ] = P 2 and T V [ i ] is a star-unit otherwise.

If x ∈ L 1 belongs to a P 2 -unit of T 1 , then an appended P 2 associated with x we call a Type-1 appended P 2 , while if x ∈ L 1 belongs to a star-unit of T 1 , then an appended P 2 associated with x we call a Type-2 appended P 2 .

For each vertex v that is the central vertex of a star-unit of T 1 , we denote the two leaf neighbors of v in T 1 that do not belong to the underlying tree T 0 by a v and b v . If a v ∈ L 1 , then a v has appended P 2 's in T and, by construction, b v remains a leaf in T (since L 1 is a 2-packing). In this case, we say that v and b v are blocked vertices . Similarly, if b v has appended P 2 's in T , then v and a v are blocked vertices. If a v and b v are both leaves of T , then only v is a blocked vertex. We shall adopt the convention that if one of a v or b v is a blocked vertex of T 1 , then renaming vertices if necessary, b v is the blocked vertex.

## 4 Main Result

By Theorem 2, every connected graph G of order n ≥ 3 satisfies γ nt ( G ) ≤ ( n +1) 2. If / T is a tree of order n ≥ 3 and γ nt ( T ) = ( n +1) 2, then by Theorem 3, / T is a subdivided star. Our aim in this paper is to characterize the trees T of order n ≥ 4 satisfying γ nt ( T ) = n/ 2. We shall prove the following result.

Theorem 5 Let T be a tree of order n ≥ 4 . If γ nt ( T ) = n/ 2 , then T ∈ T .

Proof. We proceed by induction on the order n ≥ 4 of a tree T satisfying γ nt ( T ) = n/ 2. If n = 4, then either T = P 4 or T = K 1 3 , . In both cases, γ nt ( T ) = 2 = n/ 2. If T = P 4 (respectively, T = K 1 3 , ), then T ∈ T with P 2 (respectively, K 1 ) as the unique underlying tree and the tree T itself as the corresponding base tree. This establishes the base case. Let n ≥ 6 and assume that if T ′ is a tree of order n ′ where 4 ≤ n &lt; n ′ satisfying γ nt ( T ) = n / ′ 2, then T ′ ∈ T . Let T be a tree of order n satisfying γ nt ( T ) = n/ 2. Our aim is to show that T ∈ T . For this purpose, we introduce some additional notation.

For a subtree T ′ of the tree T that belongs to the family T , we adopt the following notation in our proof. Let T ′ 0 be an underlying tree of T ′ with corresponding base tree T ′ 1 . For each vertex x ∈ V ( T ′ 1 ), we let N x = N T ′ ( x ) \ V ( T ′ 1 ), and so N x consists of all neighbors of x in T ′ that do not belong to the base tree T ′ 1 . Further, we let L x consist of all leaves of T ′ at distance 2 from x that do not belong to the base tree T ′ 1 . Necessarily, a vertex in N x is a support vertex of T ′ that belongs to a P 2 appended to x , while a vertex in L x is a leaf of T ′ that belongs to a P 2 appended to x .

Let A be the vertex set of the underlying tree T ′ 0 ; that is, A = V ( T ′ 0 ). Let B be the set of vertices in the base tree T ′ 1 that do not belong to the underlying tree T ′ 0 ; that is, B = V ( T ′ 1 ) \ V ( T ′ 0 ). Further, let B 1 be the set of all central vertices of star-units of T ′ 1 . Let C = V ( T ′ ) \ V ( T ′ 1 ) be the set of vertices of T ′ that belong to a Type-1 or Type-2 appended P 2 . We note that ( A,B,C ) is a partition of the vertex set V ( T ′ ), where possibly C = ∅ . Let C 1 (respectively, C 2 ) be the set of all leaves (respectively, support vertices) of T ′ that do not belong to the base tree T ′ 1 . We note that ( C , C 1 2 ) is a partition of the set C . Let

$$D ^ { \prime } = A \cup B _ { 1 } \cup C _ { 1 }.$$

Then the set D ′ is a NTD-set of T ′ (recall that n ′ ≥ 4). Since | D ′ | = n / ′ 2 = γ nt ( T ′ ), the set D ′ is therefore a γ nt ( T ′ )-set.

/negationslash

For each vertex x ∈ A , we let A x be the set of neighbors of x in A that have degree 2 in T ′ and belong to a P 2 -unit in T ′ 1 . Let B x be the set of all vertices in B that are neighbors of vertices in A x and let C x be the set of all vertices of C 2 that are neighbors of vertices in B x . Further, let D x be the set of all vertices of C 1 that are neighbors of vertices in C x . We note that each vertex in C x is a support vertex of T ′ that belongs to a Type-1 appended P 2 , while each vertex in D x is a leaf of T ′ that belongs to a Type-1 appended P 2 . We note that | A x | = | B x | and | C x | = | D x | , although possibly A x = ∅ (in which case B x = ). Further we ∅ let A 1 x be the set of vertices in A x that are support vertices in T ′ and we let B 1 x be the set of leaf-neighbors of vertices in A x . Possibly, A 1 x = ∅ . We note that | A 1 x | = | B 1 x | . If A x = ∅ and A x = A 1 x , then B x is the set B 1 x of leaves of T ′ (and in this case C x = D x = ). ∅

We now return to our proof of Theorem 5. If T is a star, then γ nt ( T ) = 2 &lt; n/ 2, a contradiction. If T is a double star, then the two vertices that are not leaves form a NTDset, implying that γ nt ( T ) = 2 &lt; n/ 2, a contradiction. Therefore, diam( T ) ≥ 4. Let P be a longest path in T and suppose that P is an ( r, u )-path. Necessarily, r and u are leaves in T . We now root the tree T at the vertex r . Let v be the parent of u , and let w be the parent of v in the rooted tree T . Among all such paths P , we may assume that P is chosen so that d T ( v ) is minimum. Thus if P ′ is an arbitrary longest path in T and P ′ is an ( r , u ′ ′ )-path with v ′ the neighbor of u ′ on P ′ , then d T ( v ′ ) ≥ d T ( v ).

We proceed further with the following claim.

$$\text{Claim } \mathbf A \ I f \, d _ { T } ( v ) = 2, \, t h e n \ T \in \mathcal { T }.$$

Proof of Claim A. Suppose that d T ( v ) = 2. Let T ′ = T - { u, v } have order n ′ , and so n ′ = n -2 ≥ 4. Since n is even, so too is n ′ . By Theorem 2, γ nt ( T ′ ) ≤ n / ′ 2. Let D ∗ be a γ nt ( T ′ )-set. If w ∈ D ∗ , let D = D ∗ ∪ { v } . If w / D ∈ ∗ , let D = D ∗ ∪ { u } . In both cases, the set D is a NTD-set of T , and so

$$\frac { n } { 2 } = \gamma _ { \text{nt} } ( T ) \leq | D | = | D ^ { * } | + 1 \leq \frac { n ^ { \prime } } { 2 } + 1 = \frac { n } { 2 }.$$

Hence we must have equality throughout the above inequality chain. In particular, this implies that γ nt ( T ′ ) = n / ′ 2. Applying the inductive hypothesis to the tree T ′ , we have

T ′ ∈ T . Adopting our earlier notation, let D ′ = A ∪ B 1 ∪ C 1 and recall that D ′ is a γ nt ( T ′ )-set. We now consider the parent, w , of the vertex v in the rooted tree T . If w ∈ A , then T ∈ T with T A [ ∪{ } v ] as an underlying tree of T and T A [ ∪ B ∪{ u, v } ] as the corresponding base tree. If w ∈ B and w is not a blocked vertex, then T ∈ T with T ′ 0 as an underlying tree of T and T ′ 1 as the corresponding base tree. Therefore, we may assume that either w ∈ B and w is a blocked vertex or w ∈ C , for otherwise T ∈ T as desired. We proceed further by considering the following three cases.

Case 1. w ∈ B and w is a blocked vertex. Thus, w is a blocked vertex contained in a star-unit of T ′ 1 . Let x be the vertex of A that belongs to the star-unit containing w and let y be the central vertex of the star-unit. If w ∈ B 1 (and so, w = y ), then the set

$$( D ^ { \prime } \, \sum \, ( A _ { x } ^ { 1 } \cup \{ x \} ) ) \cup ( B _ { x } ^ { 1 } \cup \{ v \} )$$

is a NTD-set of T of size | D ′ | + | B 1 x | - | A 1 x | = | D ′ | = n / ′ 2 = n/ 2 -1, implying that γ nt ( T ) &lt; n/ 2, a contradiction. Hence, w / B ∈ 1 and w is therefore a leaf-neighbor of y in the star-unit that contains it. Recall that a y and b y denote the two leaf-neighbors of y in the star-unit that do not belong to A . Since w is a blocked vertex, by convention we have w = b y . We note that at least one Type-2 P 2 is appended to a y in order for b y to be a blocked vertex. If | A | ≥ 2, then the set

$$( D ^ { \prime } \, \smallsetminus \, ( A _ { x } \cup D _ { x } \cup \{ x \} ) ) \cup ( B _ { x } \cup C _ { x } \cup \{ u \} )$$

is a NTD-set of T of size | D ′ | +( | B x | - | A x | ) + ( | C x | - | D x | ) = | D ′ | , a contradiction. Hence, A consists only of the vertex x . Thus, T ∈ T with T [ { v, w } ] as an underlying tree of T and T [ { u, v, w, x, y, a y } ] as the corresponding base tree.

Case 2. w ∈ C and w belongs to a Type1 appended P 2 . Suppose firstly that w is a leaf of T ′ , and so w ∈ C 1 . Let x be the neighbor of w that belongs to C 2 , let y be the neighbor of x that belongs to B and let z be the neighbor of y that belongs to A . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \sum \, ( A _ { z } ^ { 1 } \cup \{ w, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ u, x \} )$$

is a NTD-set of T of size | D ′ | + | B 1 z | - | A 1 z | = | D ′ | , a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case, A = A 1 z ∪{ } z , C 2 = N y and C 1 = L y . Thus, T ∈ T with T N [ y ∪{ } y ] as an underlying tree of T and T C [ ∪ { y, z } ] as the corresponding base tree.

Suppose secondly that w is a support vertex of T ′ , and so w ∈ C 2 . Let x be the leafneighbor of w in T ′ . Let y be the neighbor of w that belongs to B and let z be the neighbor of y that belongs to A . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \sum \, ( A _ { z } ^ { 1 } \cup \{ x, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ v, w \} )$$

is a NTD-set of T of size | D ′ | + | B 1 z | - | A 1 z | = | D ′ | , a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case,

A = A 1 z ∪ { z } , C 2 = N y and C 1 = L y . Thus, T ∈ T with T N [ y ∪ { v, y } ] as an underlying tree of T and T C [ ∪ { u, v, y, z } ] as the corresponding base tree.

Case 3. w ∈ C and w belongs to a Type2 appended P 2 . Suppose firstly that w is a leaf of T ′ , and so w ∈ C 1 . Let x be the neighbor of w that belongs to C 2 . Let a y be the neighbor of x that belongs to B and let y be the central vertex of the star-unit that contains a y . We note that b y is a leaf in T ′ . Let z be the neighbor of y that belongs to A . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \sum \left ( A _ { z } ^ { 1 } \cup \{ w, y, z \} \right ) ) \cup ( B _ { z } ^ { 1 } \cup \{ u, x, b _ { y } \} )$$

is a NTD-set of T of size | D ′ | , a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case, A = A 1 z ∪{ } z and C 2 = N a y . Thus, T ∈ T with T C [ 2 ∪ { a y } ] as an underlying tree of T and T C [ ∪ { y, a y , b y , z } ] as the corresponding base tree.

Suppose secondly that w is a support vertex of T ′ , and so w ∈ C 2 . Let x be the leafneighbor of w in T ′ . Let a y be the neighbor of w that belongs to B and let y be the central vertex of the star-unit that contains a y . Let z be the neighbor of y that belongs to A . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \searrow ( A _ { z } ^ { 1 } \cup \{ x, y, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ v, w, b _ { y } \} )$$

is a NTD-set of T of size | D ′ | , a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case, A = A 1 z ∪{ } z and C 2 = N a y . Thus, T ∈ T with T C [ 2 ∪{ v, a y } ] as an underlying tree of T and T C [ ∪{ u, v, y, a y , b y , z } ] as the corresponding base tree. In all three cases above, we have that T ∈ T . This completes the proof of Claim A. ( ✷ )

/negationslash

By Claim A, we may assume that d T ( v ) ≥ 3, for otherwise T ∈ T as desired. By our choice of the path P , every child of w that is not a leaf has degree at least as large as d T ( v ). Let x be the parent of w in T . Since diam( T ) ≥ 4, we note that x = r , and so d T ( x ) ≥ 2. Let w have /lscript ≥ 0 leaf-neighbors and k ≥ 1 children that are support vertices. Let W be the set consisting of the vertex w and its k children that are support vertices. Then, | W | = k +1 and, as observed earlier, every vertex in W \ { w } has degree at least d T ( v ) ≥ 3. Let the subtree, T w , of T rooted at w have order n w , and so n w ≥ 3 k + /lscript +1. Let T ′ = T -V ( T w ) be the tree obtained from T by deleting the vertices in the subtree T w of T rooted at w . Let T ′ have order n ′ . Then, n ′ ≥ 2 and n ′ = n -n w .

## Claim B If n ′ = 2 , then T ∈ T .

Proof of Claim B. Suppose that n ′ = 2. Then, n ≥ 3 k + /lscript +3 and the set W ∪ { x } is a NTD-set of T ′ , and so n/ 2 = γ nt ( T ) ≤ | W | +1 = k +2 ≤ k +( k + /lscript +3) 2 / ≤ n/ 2. Hence we must have equality throughout this inequality chain, implying that k = 1, /lscript = 0, n w = 4 and n = 6. Thus, T ∈ T with T [ { w,x } ] as the underlying tree of T and T itself as the corresponding base tree. ✷

By Claim B, we may assume that n ′ ≥ 3, for otherwise T ∈ T as desired. Applying Theorem 2 and Theorem 3 to the tree T ′ , we have that γ nt ( T ′ ) ≤ ( n ′ +1) 2, with equality / if and only if T ′ is a subdivided star.

$$\text{Claim } C \ T ^ { \prime } \in \mathcal { T }, \, d _ { T } ( w ) = 2, \, a n d \ d _ { T } ( v ) = 3.$$

Proof of Claim C. We show firstly that γ nt ( T ′ ) ≤ n / ′ 2. Suppose, to the contrary, that γ nt ( T ′ ) = ( n ′ + 1) / 2 and T ′ is a subdivided star. Let y be the link vertex of T ′ , and let Y 1 and Y 2 be the set of vertices at distance 1 and 2, respectively, from y in T ′ . Select an arbitrary vertex y 2 ∈ Y 2 and let y 1 be the common neighbor of y and y 2 , and so yy y 1 2 is a path in T ′ . Renaming vertices if necessary, we may assume that x ∈ { y, y 1 , y 2 } . If x = y , let Y = Y 2 . If x = y 1 , let Y = ( Y 2 \{ y 2 } ) ∪{ } x . If x = y 2 , let Y = ( Y 1 \{ y 1 } ) ∪{ } y . In all three cases, | Y | = ( n ′ -1) / 2 and the set W ∪ Y is a NTD-set of T . Recall that n w ≥ 3 k + /lscript +1 and n ′ = n -n w . Hence,

$$\L \L e, \quad & \gamma _ { \text{nt} } ( T ) & \leq \quad | Y | + | W | \\ & = \quad \frac { n ^ { \prime } - 1 } { 2 } + k + 1 \\ & \leq \quad \frac { n - 3 k - \ell - 2 } { 2 } + k + 1 \\ & = \quad \frac { n - k - \ell } { 2 } \\ & \leq \quad \frac { n - 1 } { 2 }, \\ \text{efore, } \gamma _ { \text{nt} } ( T ^ { \prime } ) & \leq n ^ { \prime } / 2. \text{ Every } \gamma _ { \text{nt} } ( T ^ { \prime } ) \text{-set can be } e \text{.}$$

a contradiction. Therefore, γ nt ( T ′ ) ≤ n / ′ 2. Every γ nt ( T ′ )-set can be extended to a NTD-set of T by adding to it the set W . Hence,

$$\frac { n } { 2 } = \gamma _ { \text{nt} } ( T ) \leq \gamma _ { \text{nt} } ( T ^ { \prime } ) + | W | \leq \frac { n ^ { \prime } } { 2 } + k + 1 \leq \frac { n - k - \ell + 1 } { 2 } \leq \frac { n } { 2 }.$$

Consequently, we must have equality throughout this inequality chain, implying that k = 1, /lscript = 0, d T ( w ) = 2, d T ( v ) = 3, and γ nt ( T ′ ) = n / ′ 2. Applying the inductive hypothesis to the tree T ′ of (even) order n ′ ≥ 4, we deduce that T ′ ∈ T . ✷

By Claim C, d T ( w ) = 2 and d T ( v ) = 3. Thus, N w ( ) = { v, x } . Let u 1 and u 2 be the two children of v where u = u 1 . By Claim C, T ′ ∈ T . Adopting our earlier notation, let T ′ have order n ′ . In this case, n ′ = n -4. Further, let D ′ = A ∪ B 1 ∪ C 1 and recall that D ′ is a γ nt ( T ′ )-set. We now consider the parent, x , of the vertex w in the rooted tree T . If x ∈ A , then T ∈ T with T A [ ∪ { w } ] as an underlying tree of T and T A [ ∪ B ∪ N v [ ]] as the corresponding base tree. Hence we may assume that x ∈ B ∪ C , for otherwise T ∈ T as desired.

Claim D If x ∈ B , then T ∈ T .

Proof of Claim D. Suppose that x ∈ B . We consider two subclaims.

Claim D.1 If x belongs to a P 2 -unit in T ′ 1 , then T ∈ T .

Proof of Claim D.1 Suppose that x belongs to a P 2 -unit in T ′ 1 . Let y be the neighbor of x that belongs to A . If the vertex y has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \sum \, ( A _ { y } ^ { 1 } \cup \{ y \} ) ) \cup ( B _ { y } ^ { 1 } \cup \{ v, w \} )$$

is a NTD-set of T of size | D ′ | + 1 + ( | B 1 y | - | A 1 y | ) = | D ′ | + 1 = n / ′ 2 + 1 = n/ 2 -1, a contradiction. Hence, A = { y } or every neighbor of y that belongs to A is a support vertex of degree 2 in T ′ . In this case, A = A 1 y ∪ { y } , C 2 = N x and C 1 = L x . Thus, T ∈ T with T N [ x ∪{ w,x } ] as an underlying tree of T and T C [ ∪{ u , u 1 2 , v, w, x, y } ] as the corresponding base tree. ( ✷ )

Claim D.2 If x belongs to a star-unit in T ′ 1 , then T ∈ T .

Proof of Claim D.2. Suppose that x belongs to a star-unit in T ′ 1 . Let z be the vertex of A that belongs to the star-unit containing x and let y be the central vertex of the star-unit. If x ∈ B 1 (and so, x = y ), then the set

$$( D ^ { \prime } \, \sum \, ( A _ { z } ^ { 1 } \cup \{ z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ v, w \} )$$

is a NTD-set of T of size | D ′ | +1 = n/ 2 -1, a contradiction. Hence, x / B ∈ 1 and x is therefore a leaf-neighbor in its star-unit. Recall that a y and b y denote the two leaf-neighbors of y in the star-unit that do not belong to A . By convention the vertex b y is a leaf in T ′ and the vertex a y has /lscript ≥ 0 Type-2 P 2 's appended to it.

Suppose x = a y . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \sum \, ( A _ { z } ^ { 1 } \cup \{ y, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ b _ { y }, v, w \} )$$

is a NTD-set of T of size | D ′ | + 1, a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case A = A 1 z ∪ { z } , C 2 = N a y and C 1 = L a y . Thus, T ∈ T with T C [ 2 ∪{ w,a y } ] as an underlying tree of T and T C [ ∪{ a , b y y , u 1 , u 2 , v, w, y, z } ] as the corresponding base tree.

Suppose that x = b y . If a y is a leaf of T ′ , then renaming a y and b y , we may assume that x = a y . In this case, we have shown that T ∈ T . Hence we may assume that a y has at least one Type-2 P 2 appended to it. If | A | ≥ 2, then the set

$$( D ^ { \prime } \, \smallsetminus \, ( A _ { z } \cup D _ { z } \cup \{ z \} ) ) \cup ( B _ { z } \cup C _ { z } \cup \{ v, w \} )$$

is a NTD-set of T of size | D ′ | + 1, a contradiction. Hence, A = { z } . Thus, T ∈ T with T [ { b y , w } ] as an underlying tree of T and T [ { a , b y y , u 1 , u 2 , v, w, y, z } ] as the corresponding base tree. This completes the proof of Claim D.2. ( ✷ )

Claim D now follows from Claim D.1 and Claim D.2. ✷

By Claim D, we may assume that x ∈ C , for otherwise T ∈ T as desired.

Claim E If x belongs to a Type1 appended P 2 , then T ∈ T .

Proof of Claim E. Suppose that x belongs to a Type-1 appended P 2 . Suppose firstly that x is a leaf of T ′ , and so x ∈ C 1 . Let y 2 be the neighbor of x that belongs to C 2 , let y be the neighbor of y 1 that belongs to B and let z be the neighbor of y that belongs to A . If y has degree at least 3 in T ′ , then | N y | ≥ 2 and the set

$$( D ^ { \prime } \, \smallsetminus \, ( A _ { z } ^ { 1 } \cup L _ { y } \cup \{ z \} ) ) \cup ( B _ { z } ^ { 1 } \cup ( N _ { y } \, \smallsetminus \, \{ y _ { 1 } \} ) \cup \{ v, w, y \} )$$

is a NTD-set of T of size | D ′ | +( | B 1 z |-| A 1 z | )+( | N y |-| L y | )+3 -2 = | D ′ | +1, a contradiction. Hence, y has degree 2 in T ′ . If | A | ≥ 2, then the set

$$( D ^ { \prime } \, \searrow \, ( A _ { z } \cup D _ { z } \cup \{ z \} ) ) \cup ( B _ { x } \cup C _ { x } \cup \{ v, w, y \} )$$

is a NTD-set of T of size | D ′ | +( | B x |-| A x | )+( | C x |-| D x | )+3 -2 = | D ′ | +1, a contradiction. Hence, A consists only of the vertex z . Therefore, T is obtained from the path u vwxy yz 1 1 by adding a new vertex u 2 and the edge u v 2 . Thus, T ∈ T with T [ { w,x } ] as an underlying tree of T and T [ { u , u 1 2 , v, w, x, y 1 } ] as the corresponding base tree.

Suppose secondly that x is a support vertex of T ′ , and so x ∈ C 2 . Let x 1 be the leafneighbor of x in T ′ . Let y be the neighbor of x that belongs to B and let z be the neighbor of y that belongs to A . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \sum \, ( A _ { z } ^ { 1 } \cup \{ x _ { 1 }, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ v, w, x \} )$$

is a NTD-set of T of size | D ′ | + 1, a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case, A = A 1 z ∪ { z } , C 2 = N y and C 1 = L y . Thus, T ∈ T with T N [ y ∪ { w,y } ] as an underlying tree of T and T C [ ∪{ u , u 1 2 , v, w, y, z } ] as the corresponding base tree. ✷

By Claim E, we may assume that x belongs to a Type-2 appended P 2 , for otherwise T ∈ T as desired.

Claim F The vertex x is a support vertex of T ′ .

Proof of Claim F. Suppose to the contrary that x is a leaf of T ′ , and so x ∈ C 1 . Let x 1 be the neighbor of x that belongs to C 2 . Let a y be the neighbor of x 1 that belongs to B and let y be the central vertex of the star-unit that contains a y . We note that b y is a leaf in T ′ . Let z be the neighbor of y that belongs to A . Then the set

$$( D ^ { \prime } \, \searrow \, ( A _ { z } ^ { 1 } \cup \{ x, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ v, w, a _ { y } \} )$$

is a NTD-set of T of size | D ′ | +1, a contradiction. ✷

We now return to the proof of Theorem 5 one last time. By Claim F, the vertex x is a support vertex of T ′ , and so x ∈ C 2 . Let x 1 be the leaf-neighbor of x in T ′ . Let a y be

the neighbor of x that belongs to B and let y be the central vertex of the star-unit that contains a y . Let z be the neighbor of y that belongs to A . If the vertex z has a neighbor in A that is not a support vertex of degree 2 in T ′ , then the set

$$( D ^ { \prime } \, \smallsetminus \, ( A _ { z } ^ { 1 } \cup \{ x _ { 1 }, y, z \} ) ) \cup ( B _ { z } ^ { 1 } \cup \{ v, w, x, b _ { y } \} )$$

is a NTD-set of T of size | D ′ | + 1, a contradiction. Hence, A = { z } or every neighbor of z that belongs to A is a support vertex of degree 2 in T ′ . In this case, A = A 1 z ∪ { z } and C 2 = N a y . Thus, T ∈ T with T C [ 2 ∪ { w,a y } ] as an underlying tree of T and T C [ ∪{ u , u 1 2 , v, w, y, a y , b y , z } ] as the corresponding base tree. This completes the proof of Theorem 5. ✷

## 5 Closing Remark

As a consequence of our tree characterization provided in Theorem 5, we remark that a complete solution to the Arumugam-Sivagnanam Problem 1 can be obtained as follows. Let G be a connected graph of (even) order n ≥ 4 satisfying γ nt ( G ) = n/ 2 and consider an arbitrary spanning tree T of G . By Theorem 2, γ nt ( T ) ≤ n/ 2. Every NTD-set of T is an NTD-set of G , implying that n/ 2 = γ nt ( G ) ≤ γ nt ( T ) ≤ n/ 2. Consequently, γ nt ( T ) = n/ 2. Thus, by Theorem 5, T ∈ T . This is true for every spanning tree T of the graph G . An exhaustive case analysis of the allowable edges that can be added to trees in the family T without lowering their neighborhood total domination number produces the connected graphs G of order n ≥ 4 satisfying γ nt ( G ) = n/ 2. Since our detailed case analysis of the resulting such graphs exceeds the length of the current paper, we omit the details here which can be found in [9].

## References

- [1] S. Arumugam, C. Sivagnanam, Neighborhood total domination in graphs. Opuscula Mathematica 31 (2011), 519-531.
- [2] R. C. Brigham, J. R. Carrington, and R. P. Vitray, Connected graphs with maximum total domination number. J. Combin. Comput. Combin. Math. 34 (2000), 81-96.
- [3] E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs. Networks 10 (1980), 211-219.
- [4] G. Domke, J. H. Hattingh, M. A. Henning, and L. Markus, Restrained domination in graphs with minimum degree two. J. Combin. Math. Combin. Comput. 35 (2000), 239-254.
- [5] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs , Marcel Dekker, Inc. New York, 1998.

- [6] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds), Domination in Graphs: Advanced Topics , Marcel Dekker, Inc. New York, 1998.
- [7] M. A. Henning, Recent results on total domination in graphs: A survey. Discrete Math . 309 (2009), 32-63.
- [8] M. A. Henning and N. J. Rad, Bounds on neighborhood total domination in graphs. Discrete Applied Math. 161 (2013), 2460-2466.
- [9] M. A. Henning and K. Wash, Graphs with large neighborhood total domination number, mansucript.
- [10] M. A. Henning and A. Yeo, Total domination in graphs (Springer Monographs in Mathematics) 2013. ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online).
Michael A. Henning Kirsti Wash
Trees with Large Neighborhood Total Domination Number
In this paper, we continue the study of neighborhood total domination in
graphs first studied by Arumugam and Sivagnanam [Opuscula Math. 31 (2011),
519--531]. A neighborhood total dominating set, abbreviated NTD-set, in a graph
$G$ is a dominating set $S$ in $G$ with the property that the subgraph induced
by the open neighborhood of the set $S$ has no isolated vertex. The
neighborhood total domination number, denoted by $\gnt(G)$, is the minimum
cardinality of a NTD-set of $G$. Every total dominating set is a NTD-set,
implying that $\gamma(G) \le \gnt(G) \le \gt(G)$, where $\gamma(G)$ and
$\gt(G)$ denote the domination and total domination numbers of $G$,
respectively. Arumugam and Sivagnanam posed the problem of characterizing the
connected graphs $G$ of order $n \ge 3$ achieving the largest possible
neighborhood total domination number, namely $\gnt(G) = \lceil n/2 \rceil$. A
partial solution to this problem was presented by Henning and Rad [Discrete
Applied Mathematics 161 (2013), 2460--2466] who showed that $5$-cycles and
subdivided stars are the only such graphs achieving equality in the bound when
$n$ is odd. In this paper, we characterize the extremal trees achieving
equality in the bound when $n$ is even. As a consequence of this tree
characterization, a characterization of the connected graphs achieving equality
in the bound when $n$ is even can be obtained noting that every spanning tree
of such a graph belongs to our family of extremal trees.