Pendant 3-tree-connectivity of augmented cubes

Abstract

The Steiner tree problem in graphs is widely studied because of its usefulness in network design and circuit layout. In this context, given a set of vertices $S(|S| \ge 2,)$ a tree that connects all vertices in S is called an S-Steiner tree. This helps to measure how well a network G can connect any set of S vertices together. In an S-Steiner tree, if each vertex in S has only one connection, it is called a pendant S-Steiner tree. Two pendant S-Steiner trees, T and $T',$ are internally disjoint if $E(T) \cap E(T') = \emptyset$ and $V(T) \cap V(T') = S.$ The local pendant tree-connectivity, denoted as $\tau _{G}(S),$ represents the maximum number of internally disjoint pendant S-Steiner trees in graph G. For an integer k with $2 \le k \le n,$ where n is the number of vertices, the pendant k-tree-connectivity, denoted as $\tau _{k}(G),$ is defined as $\tau _{k}(G) = min\{ \tau _{G}(S): S \subseteq V(G), |S| = k\}.$ This paper focuses on studying the pendant 3-tree-connectivity of augmented cubes, which are modified versions of hypercubes designed to enhance connectivity and reduce diameter. This research demonstrates that the pendant 3-tree-connectivity of augmented cubes, denoted as $\tau _3(AQ_n)$ is $2n-3$. This result matches the upper bound of $\tau _3(G)$ provided by Hager, specifically for the augmented cube graph $AQ_n$.

1 Introduction

Several topologies have been suggested to strike a balance between cost and performance. Among these, Cayley graphs are particularly favoured due to their appealing properties for designing interconnection networks. One widely studied Cayley graph is the hypercube denoted by $Q_n$, which is highly popular for parallel networks [1].

Augmented cubes, introduced by Choudum and Sunitha [2], are derived from hypercubes and possess favourable geometric characteristics while retaining key properties of hypercubes. An $n-$dimensional augmented cube, denoted as $AQ_n,$ extends from the hypercube $Q_n$ by adding additional links. These graphs maintain properties like vertex symmetry and facilitate routing and broadcasting procedures with linear time complexity, akin to hypercubes. Choudum and Sunitha showed that $AQ_n$ contains two edge-disjoint complete binary trees on $2^n -1$ vertices, both rooted at the same vertex. Additionally, $AQ_n$ contains all k-cycles for $3 \le k \le 2^n$. Moreover, the diameter of $AQ_n$ is approximately half that of $Q_n.$ These unique properties distinguish augmented cubes from hypercubes and other variations. Furthermore, augmented cubes are Cayley graphs, unlike all variations of hypercubes. Given these properties, $AQ_n$ emerges as a promising alternative to hypercubes for various applications.

The Steiner tree problem is of great interest to researchers in combinatorial optimization and computer science. In an augmented cube, protection routing can be established by utilizing pendant trees, as each vertex possesses a unique address. The pendant vertex of a tree ensures secure storage, making it a reliable option. These practical applications highlight the importance of investigating the pendant tree-connectivity of augmented cubes.

For a set S of vertices, with $|S| \ge 2,$ a tree that connects all the vertices in S is called an S-Steiner tree. This parameter helps to measure the reliability of a network G to connect any set of |S| vertices together.

In an S-Steiner tree connecting the vertices of set S, if each vertex in S has a degree one, the tree is called a pendant S-Steiner tree. Two pendant S-Steiner trees T and $T'$ are internally disjoint if $E(T) \cap E(T') = \emptyset$ and $V(T) \cap V(T') = S.$ The local pendant tree-connectivity $\tau _{G}(S)$ refers to the maximum number of internally disjoint pendant S-Steiner trees in graph G. For any integer k ($2 \le k \le n$), the pendant k-tree-connectivity $\tau _{k}(G)$ is defined as $\tau _{k}(G) = min\{ \tau _{G}(S): S \subseteq V(G), |S| = k\}.$

The concept of pendant tree-connectivity, introduced by Hager [3], is a specific case of generalized connectivity, which itself is a broader concept introduced by Chartrand [4]. Generalized connectivity, also known as k-tree-connectivity, is a generalization of classical connectivity. In the definition of pendant tree-connectivity, if we relax the requirement for each vertex in S to have a degree one, it transforms into generalized connectivity.

The generalized 2-connectivity, denoted as $\kappa _2(G),$ is equivalent to the connectivity $\kappa (G)$ of graph G. Furthermore, $\kappa _n(G)$ corresponds precisely to the spanning tree packing number of G. Thus, generalized connectivity serves as a unified concept encompassing both classical connectivity and spanning tree packing number. In our work [5], we proved that $\kappa _3(AQ_n)= 2n-2.$ In 2017,  L. Chen et al. [6] established the hardness of determining the generalized connectivity of a given graph G.

Theorem 1.1

[6] Given a graph G and a 3-subset S of V(G) and an integer $l~ (2 \le l \le n-2),$ deciding whether there are l internally disjoint trees containing S,  namely deciding whether $\kappa _G(S) \ge l,$ is NP-complete.

Since pendant S-Steiner trees are a special type of S-Steiner trees, determining whether $\tau _G(S) \ge l$ for $2 \le l \le n-2$ is also NP-complete.

The close relationships between generalized connectivity and complete independent spanning trees (CISTs), as well as disjoint paths, are well established. Research on S-Steiner trees, CISTs, spanning tree packing numbers, generalized connectivity, and pendant tree-connectivity of graphs is crucial for optimizing information transportation in large-scale networks, particularly in parallel routing design. Furthermore, this research offers valuable insights for evaluating fault tolerance, see [7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40].

As a bridge between discrete mathematics and theoretical computer science, algorithmic graph theory has gained significant importance in recent years. In our work, we demonstrate that $\tau _3(AQ_n) = 2n-3,$ reaching the upper bound of $\tau _3(G)$ as established by Hager [3], for $G = AQ_n$.

2 Preliminaries

The n-dimensional augmented cube, denoted by $AQ_n, n\ge 1,$ is a graph with a vertex set consisting of all binary n-tuples, represented as $\{0, 1\}^n$. This graph is defined recursively as follows.

$AQ_1$ is the complete graph $K_2$ with vertex set $\{0, 1\}.$ For $n \ge 2,~ AQ_n$ is obtained from two copies of $AQ_{n-1},$ denoted as $AQ^0_{n-1}$ and $AQ^1_{n-1},$ and then adding $2^n$ edges between them as follows.

Let $V(AQ^0_{n-1}) = \{ 0x_1x_2...x_{n-1} :x_i = 0~~ \textrm{or}~~ 1\}$ and $V(AQ^1_{n-1}) = \{1y_1y_2...y_{n-1} :y_i = 0~~ \textrm{or}~~ 1\}.$ A vertex $x = 0x_1x_2...x_{n-1}$ of $AQ^0_{n-1}$ is joined to a vertex $y = 1y_1y_2...y_{n-1}$ of $AQ^1_{n-1}$ if and only if either

• (1) $x_i = y_i$ for $1 \le i \le n-1,$ in this case the edge xy is called a hypercube edge and we set $y = x^h$ or

• (2) $x_i = \overline{y_i}$ for $1 \le i \le n-1,$ in this case the edge xy is called a complementary edge and we set $y = x^c.$

Notice that for any $x \in V(AQ_n),$ we have $(x^c)^h = (x^h)^c = x^{ch}$ (let us call it $x^{ch}$).

Let $E_n^h$ and $E_n^c$ denote the sets of hypercube edges and complementary edges, respectively, used to construct $AQ_n$ from two copies of $AQ_{n-1}.$ Then, $E_n^h$ and $E_n^c$ form perfect matchings of $AQ_n,$ and furthermore, $AQ_n = AQ^0_{n-1} \cup AQ^1_{n-1} \cup E_n^h \cup E_n^c.$

The augmented cubes of dimensions 1, 2, and 3 are depicted in Fig. 1.

Fig. 1

Augmented cubes of dimensions 1, 2, and 3

In $AQ_3,$ if $u_1 = 000, u_2 = 001, u_3 = 011, u_4 = 010$ and $v_1 =100, v_2 = 101, v_3 = 111, v_4 =110$, then $E_3^h = \{u_iv_i: i = 1, 2, 3, 4\}$ and $E_3^c = \{ u_1v_3, u_2v_4, u_3v_1, u_4v_2\}.$

From the definition, it is clear that $AQ_n$ is a $(2n-1)$-regular graph with $2^n$ vertices. Additionally, $AQ_n$ is known to be $(2n-1)$-connected and vertex-transitive [2].

3 Pendant 3-tree-connectivity of augmented cubes, ${\tau _3(AQ_n)}$

With Hager’s introduction of tree-connectivity, another tree-connectivity parameter called pendant tree-connectivity was also proposed in his work [3]. Recently, Mao [26, 27] has further explored pendant tree-connectivity. In this section, we aim to determine the pendant 3-tree-connectivity of $AQ_n.$ Before proceeding, let us review some definitions necessary for our discussion.

Definition 3.1

([3]) For an S-Steiner tree, if the degree of each vertex in S is equal to one, then that tree is called a pendant S-Steiner tree.

Two pendant S-Steiner trees T and $T'$ are said to be internally disjoint if $E(T) \cap E(T') = \emptyset$ and $V(T) \cap V(T') = S.$ For $S \subseteq V(G)$ and $|S| \ge 2,$ the local pendant tree-connectivity $\tau _{G}(S)$ is the maximum number of internally disjoint pendant S-Steiner trees in G. For an integer k with $2 \le k \le n,$ the pendant k-tree-connectivity is defined as

$$\tau _{k}(G) = min\{ \tau _{G}(S): S \subseteq V(G), |S| = k\}.$$

By convention, $\tau _{k}(G) = 0$ when G is disconnected.

Fig. 2

Pendant S-Steiner trees in $AQ_3$

In Fig. 2a, there are three pendant S-Steiner trees in $AQ_3,$ where $S = \{000, 001, 011\}$. Additionally, in Fig. 2b, we observe four pendant S-Steiner trees in $AQ_3$ with $S = \{001, 010, 100\}.$

Note that $\tau _{1}(AQ_n)$ is equal to the order of $AQ_n,$ i.e. $2n-1.$ Additionally, $\tau _{2}(AQ_n) = 2n-1,$ since the augmented cube is $(2n-1)$-connected. It is evident that $\tau _{k}(G) \le \kappa _{k}(G),~ k \ge 2.$ For the augmented cube $AQ_n,$ we have $\tau _{3}(AQ_n) \le \kappa _{3}(AQ_n) = 2n - 2.$

Let S be the vertex set of a triangle in $AQ_n.$ In this scenario, we cannot use the two edges from each vertex in S to the other two vertices of S in the construction of pendant S-Steiner trees, as the vertices of S should be pendant in each tree. Thus, in this case, we can obtain at most $2n - 3$ pendant S-Steiner trees. Hence, $\displaystyle \tau _{3}(AQ_n) \le 2n-3.$

In this section, we establish the existence of $2n - 3$ pendant S-Steiner trees in $AQ_n$ for any subset $S \subset V(AQ_n)$ with $|S| = 3.$ Hence, the result is optimal.

Hager [3] provided the following result regarding pendant k-tree-connectivity, $\tau _k(G)$, of a simple, finite graph G.

Proposition 3.2

([3]) Let G be a graph with $\tau _k(G) \ge m.$ Then, $\delta (G) \ge k + m - 1.$

We need the above Proposition to prove the next result regarding the pendant 3-tree-connectivity of the augmented cube $AQ_n.$ Additionally, we require the following result concerning the existence of a one-to-one path covering between any two vertices of the augmented cube, i.e. between any two vertices of $AQ_n$, there exist k vertex-disjoint paths covering all its vertices, for $2 \le k \le 2n-1$. Since the maximum order of a one-to-one path cover in the augmented cube is equal to its connectivity, which is $(2n-1),$ $AQ_n$ becomes super spanning connected.

Proposition 3.3

([18]) $AQ_n$ is super spanning connected if and only if $n \ne 3$.

We now explore the main result of this paper.

Theorem 3.4

Let $n \ge 3$ be an integer. The pendant 3-tree-connectivity $\tau _3(AQ_n)$ of $AQ_n$ is $2n - 3.$

Proof

The contra-positive statement of the above Proposition 3.2 is:

Let G be a graph with $\delta (G) < k + m - 1.$ Then, $\tau _k(G) < m.$

Given that $\delta (AQ_n)= 2n-1 < 3 + 2n - 2 - 1,$ we can infer from the previous result that $\tau _3(AQ_n) < 2n - 2,$ which implies $\tau _3(AQ_n) \le 2n - 3.$ Therefore, it is sufficient to demonstrate that for any subset S of $V(AQ_n)$ with $|S| = 3,$ there exist $2n - 3$ pendant S-Steiner trees in $AQ_n$.

To prove this result, we will use induction on n. Let us start with the base case, $n = 3.$ Since $AQ_n$ is vertex-transitive according to [2], we can confirm the validity of the result for $n = 3$ from the following figures (Fig. 3a).

Fig. 3

a Pendant S-Steiner trees in $AQ_3$. b Pendant S-Steiner trees in $AQ_4$

The figures above include every option of three vertex sets in $AQ_4$, ensuring the truth of the result for both $n=3$ and $n=4$. Assuming the induction hypothesis holds, the result remains true for $AQ_{n-1}$ , i.e. $\tau _3(AQ_{n-1}) = 2n - 5.$ Let us break down the canonical representation of $AQ_n$ as follows: $AQ_n = AQ^0_{n-1} \cup AQ^1_{n-1} \cup E^h_n \cup E^c_n$. Let $S = \{ x, y, z\}$ be a subset of $V(AQ_n).$

Case 1: Suppose $x, y, z \in V(AQ^0_{n-1}).$

Utilizing the induction hypothesis, we derive that there are $2n - 5$ S-Steiner trees present in $AQ_{n-1}^0$. Now in $AQ_{n-1}^1,~ x^h$ is the complement of $x^c.$ As we have the decomposition of $AQ^1_{n-1}$ into two subgraphs, namely $AQ^{10}_{n-2}$ and $AQ^{11}_{n-2},$ one of the vertices $x^h$ and $x^c$ should lie in $AQ^{10}_{n-2}$ and other in $AQ^{11}_{n-2}.$ Similar is true for $\{y^h, y^c\}$ and $\{z^h, z^c\}.$ Thus, one of the neighbours, either hypercubic or complement, of each vertex of S lies in $A^{10}_{n-2}$ and other in $AQ^{11}_{n-2}.$ Since $AQ_n$ is Hamiltonian, there exist Hamiltonian paths $P_1$ in $AQ^{10}_{n-2}$ and $P_2$ in $AQ^{11}_{n-2}.$ Hence, joining x, y, and z to their neighbours on $P_1$ and on $P_2$ , we get two more pendant S-Steiner trees. Thus, in this case, we get $2n - 3$ pendant S-Steiner trees in $AQ_n,$ see Fig. 4.

Fig. 4

Illustration for Case 1

Likewise, due to the vertex transitivity of the augmented cube, we will obtain $2n - 3$ pendant S-Steiner trees within $AQ_n$, when $\{x, y, z\} \subseteq V(AQ^1_{n-1}).$

Case 2: Suppose $\{x, y\} \subseteq V(AQ^0_{n-1})$ and $z \in V(AQ^1_{n-1}).$

Subcase 2.1: Let $z \in \{x^h, x^c, y^h, y^c\}.$

Without loss of generality, suppose $z = x^h.$

Subcase 2.1.1: Suppose $\{x^h, x^c\} = \{y^h, y^c\}.$

Consequently, in this scenario, x is adjacent to y. According to Proposition 3.3, we establish a path cover between x and y, denoted as $P_1, P_2, \dots , P_{2n-3}$ within $AQ_{n-1}^0$. Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Without loss of generality, suppose $y_1 = x.$ Then, $y_1^c= x^c= y^h \in V(AQ_{n - 1}^1).$ Let $Q_1, Q_2, \dots , Q_{2n - 3}$ be the path cover between $z(=x^h)$ and $y^h$ in $AQ_{n - 1}^1$ corresponding to the path cover $\{P_1, P_2, \dots , P_{2n-3}\}$ of $AQ_{n-1}^0.$ Clearly, the neighbours $y^c_1, y^c_2, \dots , y^c_{2n -3}$ of $y^c$ lie on the paths $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively, and hence, $Q_1 = y^c x^c.$ Thus, the required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are as follows:

$T_i = P_i \cup \{ y^cy_i^c,~ y_iy^c_i\},$ for $2 \le i \le 2n -3$ and $T_1 = \{ x y^h,~ yy^h \} \cup \; Q_1,$ see Fig. 5.

Fig. 5

Illustration for Subcase 2.1.1

Subcase 2.1.2:

Let us assume that $\{x^h, x^c\} \ne \{y^h, y^c\}$ and z is not adjacent to either $y^h$ or $y^c$.

Clearly, x is not adjacent to y since $z=x^h$ and z is not adjacent $y^h.$ We know that $AQ_n$ has one-to-one path cover of order k, $1 \le k \le 2n - 1$ between any pair of vertices. Therefore, we get a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. In $AQ_{n-1}^1,$ let $Q_1, Q_2, \dots , Q_{2n - 3}$ be the corresponding path cover between $z= x^h$ and $y^h$ such that $y^h_1, y^h_2, \dots , y^h_{2n -3}$ are neighbours of $y^h$ along $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Thus, the required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are obtained as follows:

$T_i = P_i \cup \{Q_i\backslash y^hy_i^h\} ~\cup ~ \{y_iy^h_i\},$ for $1 \le i \le 2n -3,$ see Fig. 6.

Fig. 6

Illustration for Subcase 2.1.2

Subcase 2.1.3: Let us suppose that $\{x^h, x^c\} \ne \{y^h, y^c\}$ and z is adjacent to $y^h$ or both $y^h$ and $y^c$ in $AQ_{n-1}^1$.

Then, y is adjacent to $z^h= x$ in $AQ_{n-1}^0.$ By Proposition 3.3, we get one-to-one path cover of order k, $1 \le k \le 2n - 1$ between any pair of vertices in $AQ_n$. Thus, we get a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $x_1, x_2, \dots , x_{2n-3}$ be the neighbours of x along $P_1, P_2, \dots , P_{2n-3}$, respectively. Similarly, in $AQ_{n-1}^1,$ we get a path cover $Q_1, Q_2, \dots , Q_{2n - 3}$ between $x^c$ and z such that neighbours $x^c_1, x^c_2, \dots , x^c_{2n -3}$ of $x^c$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Since x is adjacent to y in $AQ^0_{n-1},$ without loss of generality, we assume that $x_1 = y$ which gives $x_1^c = y^c$ in $AQ^1_{n-1}.$ Also, without loss of generality, assume that $x_2 = x^{ch}$ in $AQ^0_{n-1}.$ Hence, $P_1 = \,\,x y$ and $Q_2 =\,\, x^c x^h.$ The required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are as follows:

$T_i = P_i \cup \{Q_i\backslash x^c x_i^c \}~ \cup \{ x_i x^c_i \},$ for $3 \le i \le 2n -3,$

$T_1 = P_2 ~\cup \{x_2 z\}$ and $T_2 =~\{ x x^c,~ y y^c\} \cup ~ Q_1,$ see Fig. 7.

Fig. 7

Illustration for Subcase 2.1.3

Subcase 2.1.4: Suppose $\{x^h, x^c\} \ne \{y^h, y^c\}$ and z is adjacent to $y^c$ but not adjacent to $y^h$ in $AQ_{n-1}^1.$

Then, using the same reasoning as in Subcase 2.1.2 of this theorem, we obtain the necessary $2n - 3$ pendant S-Steiner trees, as shown in Fig. 6. In this situation, assuming without loss of generality that $y^c= y_1^h$, the path $Q_1$ would be $\{y^h y^c, y^c z\}$.

Similarly, we get $2n-3$ pendant S-Steiner trees in the augmented cube $AQ_n$ if $z = x^c, y^c$ or $y^h.$

Subcase 2.2: Let $z \notin \{x^c, x^h, y^c, y^h\}.$

Subcase 2.2.1: Let us examine the scenario where $\{x^h, x^c\} = \{y^h, y^c\}$. Notice that in this instance, x is adjacent to y, and $x^h = y^c$ while $x^c= y^h$.

Subcase 2.2.1(a): Let us assume that z is adjacent to one of the vertices $x^h$ or $x^c$, but not both.

Without loss of generality, suppose z is adjacent to $x^c.$ Now we have a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Without loss of generality, suppose $y_1 = x.$ Thus, $P_1 =\,\,x y.$ Then, $y_1^c= x^c=y^h \in AQ_{n - 1}^1.$ Consider a path cover $Q_1, Q_2, \dots , Q_{2n-3}$ between $y^c(= x^h)$ and z such that neighbours $y^c_1, y^c_2, \dots , y^c_{2n -3}$ of $y^c$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Thus, the required $2n-3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are as follows:

$T_i = P_i \cup \{Q_i\backslash \{y^c y_i^c\}\}~ \cup \{y_i y^c_i\},$ for $2 \le i \le 2n -3,$

$T_1 =\,\, \{x x^c,~ y y^h\} \cup ~\{Q_1 \backslash \{x^c x^h\}\},$ see Fig. 8.

Fig. 8

Illustration for Subcase 2.2.1(a)

Subcase 2.2.1(b): Let us consider the case where z is adjacent to both $x^h$ and $x^c$.

Since z is adjacent to $x^h = y^c$ in $AQ_{n-1}^1, \,\, z^c$ is adjacent to y in $AQ_{n-1}^0.$ Now we have a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Without loss of generality, suppose $y_1 = z^c$ and $y_2 = x.$ Thus, $P_2 = x y.$ Then, $y_1^c= z$ and $y_2^c = x^c$ in $AQ_{n - 1}^1.$ Consider a path cover $Q_1, Q_2, \dots , Q_{2n - 3}$ between $y^c(= x^h)$ and z such that the neighbours $y^c_1, y^c_2, \dots , y^c_{2n -3}$ of $y^c$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. The required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are as follows:

$T_i = P_i ~\cup \{Q_i\backslash \{y^c y_i^c\}\}~ \cup \{y_i y^c_i\},$ for $3 \le i \le 2n -3,$

$T_1 = P_1~ \cup \{ z^c z\}$ and $T_2 = \,\,Q_2 \cup ~ \{x x^h,~ y y^h\},$ see Fig. 9.

Fig. 9

Illustration for Subcase 2.2.1(b)

Subcase 2.2.1(c): Let us suppose that z is not adjacent to both $x^c$ and $x^h$.

By Proposition 3.3, we get a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ^0_{n-1}$. Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Since x is adjacent to y,  without loss of generality, suppose $y_1 = x$ , and hence, $P_1 = x y.$ Consider a path cover $Q_1, Q_2, \dots , Q_{2n - 3}$ between $y^h(= x^c)$ and z such that the neighbours $y^h_1, y^h_2, \dots , y^h_{2n -3}$ of $y^h$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Thus, $y^h_1 = x^h = y^c.$ The required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are as follows:

$T_i = P_i ~\cup \{Q_i\backslash \{y^h y_i^h\}\}~ \cup \{y_i y^h_i\},$ for $2 \le i \le 2n -3,$

$T_1 = Q_1~ \cup \{y y^h, x x^h\},$ see Fig. 10.

Fig. 10

Illustration for Subcase 2.2.1(c)

Subcase 2.2.2: Suppose $\{x^h, x^c\} \ne \{y^h, y^c\}$ and x is not adjacent to y.

Subcase 2.2.2(a): If z is adjacent to all $x^h, x^c, y^h,$ and $y^c.$

Since z is adjacent to $y^c$ and $x^c$ in $AQ_{n-1}^1, \,\, z^c$ is adjacent to y and x in $AQ_{n-1}^0.$ Now we have a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Let $Q_1, Q_2, \dots , Q_{2n - 3}$ be a path cover between $y^c$ and z in $AQ^1_{n-1}$ such that the neighbours $y^c_1, y^c_2, \dots , y^c_{2n -3}$ of $y^c$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Without loss of generality, suppose $y_1 = z^c$ and $y_2 = y^{ch}.$ Then, $y_1^c= z$ and $y_2^c = y^h$ in $AQ_{n - 1}^1.$ The required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are as follows:

$T_i = P_i ~\cup \{Q_i\backslash \{y^c y_i^c\}\} \cup \{y_i y^c_i\},$ for $3 \le i \le 2n -3,$

$T_1 = P_1~ \cup \{ z^c z\}$ and $T_2 = \,\,\{P_2\backslash \{y y^{ch}\}\} \cup Q_2 \cup \{y^cy^{ch},~ y y^h\},$ see Fig. 11.

Fig. 11

Illustration for Subcase 2.2.2(a)

Subcase 2.2.2(b): If z is not adjacent to all of $x^h$, $x^c$, $y^h$, and $y^c$.

By Proposition 3.3, we get a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. In $AQ_{n-1}^1,$ let $Q_1, Q_2, \dots , Q_{2n - 3}$ be a path cover between z and $y^h$ in $AQ_{n-1}^1$ such that $y^h_1, y^h_2, \dots , y^h_{2n -3}$ are neighbours of $y^h$ along $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Thus, the required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are obtained as follows:

$T_i = P_i \cup \{Q_i\backslash \{y^hy_i^h\}\} ~\cup ~ \{y_iy^h_i\},$ for $1 \le i \le 2n -3,$ see Fig. 12.

Fig. 12

Illustration for Subcase 2.2.2(b)

With the same line of reasoning, we derive $2n-3$ pendant S-Steiner trees in $AQ_n$ for the described cases.

• (i) z is adjacent to $y^c$ or $x^c$ or both, but not adjacent to $y^h$ or $x^h$.

• (ii) z is adjacent to $y^c$ or $x^h$ or both, but not adjacent to $y^h$ or $x^c$.

In the aforementioned argument, if we opt for a path cover between $y^c$ and z instead of between $y^h$ and z in $AQ^1_{n-1}$, we still obtain $2n-3$ pendant S-Steiner trees in $AQ_n$ for the described cases.

• (i) z is adjacent to $y^h$ or $x^h$ or both, but not adjacent to $y^c, x^c.$

• (ii) z is adjacent to $y^h$ or $x^c$ or both, but not adjacent to $y^c, x^h.$

Subcase 2.2.2(c): If z is adjacent to $y^c$ or $y^h$ or both, but not adjacent to $x^h$ and $x^c$.

In this scenario, employ a path cover of order $2n -3$ between $x^h$ and z instead of between $y^h$ and z in $AQ_{n-1}^1$ and obtain the desired result similar to Subcase 2.2.2(b), as depicted in Fig. 13.

Fig. 13

Illustration for Subcase 2.2.2(c)

Similarly, we obtain $2n - 3$ pendant S-Steiner trees if z is adjacent to $x^h$ or $x^c$ or both, but not adjacent to $y^h$ and $y^c$.

Subcase 2.2.2(d): Suppose z is adjacent to $y^h$ only or to $y^h, x^c, x^h.$

In this case, use a path cover of order $2n -3$ between $y^c$ and z instead of between $y^h$ and z in $AQ_{n-1}^1$ and get the required result as similar to Subcase 2.2.2(b). Similarly, we get $2n - 3$ pendant S-Steiner trees if z is adjacent to $x^h$ only or to $x^h,~ y^c,~ y^h.$

Subcase 2.2.2(e): Suppose z is not adjacent to $y^h$ only or to $y^c, x^h, x^c.$

In this case, if z is not adjacent to $y^h$ only then as similar to Subcase 2.2.2(b), we get required $2n-3$ pendant S-Steiner trees in $AQ_n$ by using a path cover of order $2n -3$ between $y^h$ and z in $AQ_{n-1}^1.$ If z is not adjacent to $y^c, x^h, x^c$ , then we get required $2n-3$ pendant S-Steiner trees in $AQ_n$ as similar to Subcase 2.2.2(b) by using a path cover of order $2n -3$ between $y^c$ and z instead of $y^h$ and z in $AQ_{n-1}^1.$

Subcase 2.2.3: Assume now that $\{x^h, x^c\} \ne \{y^h, y^c\}$ and x is adjacent to y.

Subcase 2.2.3(a): Suppose z is adjacent to all $x^h, x^c, y^h$ and $y^c.$

We have a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Since z is adjacent to $y^h$ in $AQ^1_{n-1},$ $z^h$ is adjacent to y in $AQ^0_{n-1}.$ Without loss of generality, suppose $y_1 = z^h.$ Hence, $y_1^h = z$. Since x is adjacent to y,  let us assume, without any loss of generality, that $y_2 = x.$ Thus, $y_2^h = x^h$. Also, take $y_3= y^{ch}$ in $AQ^0_{n-1}$ so that $y_3^h= y^{c}$ in $AQ^1_{n-1}.$ Now, in $AQ_{n-1}^1,$ we get a path cover $Q_1, Q_2, \dots , Q_{2n - 3}$ between $y^h$ and z such that the neighbours $y^h_1, y^h_2, \dots , y^h_{2n -3}$ of $y^h$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Thus, the required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are obtained as follows:

$T_i = P_i \cup \{Q_i\backslash \{y^h y_i^h\}\}~ \cup \{y_i y^h_i\},$ for $4 \le i \le 2n -3$ and

$T_1 = \,\,P_1 \cup ~\{z z^h\},$ $T_2 = \,\,Q_2 \cup ~\{x x^h, ~y y^h\}$

$T_3 = \,\,P_3 \cup \{Q_3\backslash \{y^h y^c\}\} \cup ~\{y^c y^{ch}\},$ see Fig. 14.

Fig. 14

Illustration for Subcase 2.2.3(a)

Subcase 2.2.3(b): Suppose z is not adjacent to all $x^h, x^c, y^h$ and $y^c.$

We have a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0.$ Let $y_1, y_2, \dots , y_{2n-3}$ be the neighbours of y along $P_1, P_2, \dots , P_{2n-3}$, respectively. Since x is adjacent to y,  without loss of generality, suppose $y_1 = x.$ Hence, $y_1^h = x^h$. Now, in $AQ_{n-1}^1,$ we get a path cover $Q_1, Q_2, \dots , Q_{2n - 3}$ between $y^h$ and z such that the neighbours $y^h_1, y^h_2, \dots , y^h_{2n -3}$ of $y^h$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Thus, the required $2n - 3$ pendant S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are obtained as follows:

$T_i = P_i \cup \{Q_i\backslash \{y^h y_i^h\}\}~ \cup \{y_i y^h_i\},$ for $2 \le i \le 2n -3$ and

$T_1 = \,\,Q_1 \cup ~\{x x^h, ~y y^h\},$ see Fig. 15.

Fig. 15

Illustration for Subcase 2.2.3(b)

With the same argument, we get $2n-3$ pendant S-Steiner trees in $AQ_n$ for the following cases:

• (i) z is adjacent to $y^c$ or $x^c$ or both, but not adjacent to $y^h, x^h.$

• (ii) z is adjacent to $y^c$ or $x^h$ or both, but not adjacent to $y^h, x^c.$

In the above argument, if we take a path cover between $y^c$ and z instead of between $y^h$ and z in $AQ^1_{n-1}$ , then we also get $2n-3$ pendant S-Steiner trees in $AQ_n$ for the following cases:

• (i) z is adjacent to $y^h$ or $x^h$ or both, but not adjacent to $y^c, x^c.$

• (ii) z is adjacent to $y^h$ or $x^c$ or both, but not adjacent to $y^c, x^h.$

Subcase 2.2.3(c): Suppose z is adjacent $y^c$ or $y^h$ or both, but not adjacent to $x^h$ and $x^c$.

We establish a path cover $P_1, P_2, \dots , P_{2n-3}$ between x and y in $AQ_{n-1}^0$. Let us denote the neighbours of x along $P_1, P_2, \dots , P_{2n-3}$ by $x_1, x_2, \dots , x_{2n-3}$, respectively. Let $Q_1, Q_2, \dots , Q_{2n - 3}$ be a path cover between $x^h$ and z in $AQ_{n-1}^1$ such that neighbours $x^h_1, x^h_2, \dots , x^h_{2n -3}$ of $x^h$ lie on $Q_1, Q_2, \dots , Q_{2n - 3}$, respectively. Since x is adjacent to y,  without loss of generality, suppose $x_1 = y,$ which gives us $P_1 = x y$ and $x_1^h = y^h.$ Thus, the required $2n - 3$ S-Steiner trees $T_1, T_2, \dots , T_{2n -3}$ are constructed as follows:

$T_i = P_i \cup \{Q_i\backslash \{x^h x_i^h\}\}~ \cup \{x_i x^h_i\},$ for $2 \le i \le 2n -3$ and

$T_1 =\,\, Q_1 \cup ~ \{x x^h,~ y y^h\},$ see Fig. 16.

Fig. 16

Illustration for Subcase 2.2.3(c)

Similarly, we obtain $2n - 3$ pendant S-Steiner trees if z is adjacent to $x^h$ or $x^c$ or both, but not adjacent to $y^h$ and $y^c$.

Subcase 2.2.3(d): Suppose z is adjacent to $y^h$ only or to $y^h, x^c, x^h.$

In this case, utilize a path cover of order $2n -3$ between $y^c$ and z instead of between $y^h$ and z in $AQ_{n-1}^1$ to achieve the desired outcome, akin to Subcase 2.2.3(b). Likewise, we obtain $2n - 3$ pendant S-Steiner trees if z is adjacent to $x^h$ only or to $x^h$, $y^c$, and $y^h$.

Subcase 2.2.3(e): Suppose z is not adjacent to $y^h$ only or to $y^c, x^h, x^c.$

In this case, if z is not adjacent to $y^h$ only then as similar to Subcase 2.2.3(b), we get required $2n-3$ pendant S-Steiner trees in $AQ_n$ by using a path cover of order $2n -3$ between $y^h$ and z in $AQ_{n-1}^1.$ If z is not adjacent to $y^c, x^h, x^c$ , then we get required $2n-3$ pendant S-Steiner trees in $AQ_n$ as similar to Subcase 2.2.3(b) by using a path cover of order $2n -3$ between $y^c$ and z instead of between $y^h$ and z in $AQ_{n-1}^1.$

Therefore, utilizing the vertex transitivity of the augmented cube, we obtain $2n - 3$ pendant S-Steiner trees in $AQ_n$, similarly when $\{x, y\} \subseteq V(AQ^1_{n-1})$ and $z \in V(AQ^0_{n-1})$.

Thus, by the principle of mathematical induction, we conclude that $\tau _{3}(AQ_n) = 2n - 3$.

4 Concluding remarks

In this paper, pendant 3-tree-connectivity of $AQ_n$ is established, indicating $\tau _3(AQ_n) = 2n -3$. However, evaluations of $\tau _k(AQ_n)$ for $k \ge 4$ remain open.