The girth vertex (resp. edge) tenacity g τ v ( G ) (resp. g τ e ( G ) ) of a non-acyclic simple graph G is defined to be the maximum number k such that the removal of any k vertices (resp. edges) of G does not change its girth. In this paper, we mainly investigated the girth tenacity of the exchanged hypercube E H ( s , t ) with s , t ≥ 1 , the ternary n -cube Q n 3 and the exchanged ternary n -cube E 3 C ( r , s , t ) with n = r + s + t and r , s , t ≥ 0 . We proved that ( i ) g τ v ( E H ( 1 , 1 ) ) = 0 , g τ v ( E H ( s , t ) ) = 2 ⌊ 2 t + 1 3 ⌋ − 1 for s = 1 and t ≥ 2 , g τ v ( E H ( s , t ) ) = 2 ⌊ 2 s + 1 3 ⌋ − 1 for t = 1 and s ≥ 2 , g τ v ( E H ( s , t ) ) = ⌊ 2 t + 1 3 ⌋ 2 s + ⌊ 2 s + 1 3 ⌋ 2 t − 1 for min { s , t } ≥ 2 , and ( i i ) g τ v ( Q n 3 ) = 3 n − 1 − 1 , g τ e ( Q n 3 ) = n 3 n − 1 − 1 , and ( i i i ) g τ v ( E 3 C ( r , s , t ) ) = 3 n − 1 − 1 , g τ e ( E 3 C ( r , s , t ) ) = ( n + 2 ) 3 n − 2 − 1 . Some results on the girth tenacity of the hypercube were also listed.

Let G be a connected graph and S ⊆ V ( G ) with | S | ≥ 2 . A tree T in G is called an S -tree if S ⊆ V ( T ) . Two S -trees T 1 and T 2 are called internally disjoint if E ( T 1 ) ∩ E ( T 2 ) = 0̸ and V ( T 1 ) ∩ V ( T 2 ) = S . For an integer k with 2 ≤ k ≤ n , the generalized k -connectivity of a graph G is defined as κ k ( G ) = min { κ G ( S ) | S ⊆ V ( G ) and | S | = k } , where κ G ( S ) denotes the maximum number of internally disjoint S -trees in G . The generalized k -connectivity extends traditional connectivity and serves as a crucial measure for evaluating the reliability and fault tolerance of connecting any k vertices in G . In this paper, we mainly investigate the generalized 4-connectivity of a family of regular graph G n , which improves the known results about generalized 3-connectivity of G n in Zhao et al., (2021). For a reason that the alternating group network A N n , the star graph S n and pancake graphs P n are special cases of the regular graph G n , as applications of the main result, we obtain that κ 4 ( A N n ) = n − 2 for n ≥ 4 , κ 4 ( S n ) = n − 2 for n ≥ 3 and κ 4 ( P n ) = n − 2 for n ≥ 3 .

Abstract The generalized $k$-connectivity of a graph $G$ is a parameter that can measure the reliability of a network $G$ to connect any $k$ vertices in $G$, which is a generalization of traditional connectivity. Let $S\subseteq V(G)$ and $\kappa _{G}(S)$ denote the maximum number $r$ of edge-disjoint trees $T_{1}, T_{2}, \cdots , T_{r}$ in $G$ such that $V(T_{i})\bigcap V(T_{j})=S$ for any $i, j \in \{1, 2, \cdots , r\}$ and $i\neq j$. For an integer $k$ with $2\leq k\leq n$, the generalized $k$-connectivity of a graph $G$ is defined as $\kappa _{k}(G)= min\{\kappa _{G}(S)|S\subseteq V(G)$ and $|S|=k\}$. In this paper, we introduce a family of regular graph $G_{n}$ that can be constructed recursively and each vertex with exactly one outside neighbor. The generalized $3$-connectivity of the regular graph $G_{n}$ is studied, which attains a previously proven upper bound on $\kappa _{3}(G)$. As applications of the main result, the generalized $3$-connectivity of some important networks including some known results such as the alternating group network $AN_{n}$, the star graph $S_{n}$ and the pancake graphs $P_{n}$ can be obtained directly.

Let S⊆V(G) and κG(S) denote the maximum number r of edge-disjoint trees T1,T2,…,Tr in G such that V(Ti)∩V(Tj)=S for any i,j∈{1,2,…,r} and i≠j⁠. For an integer k with 2≤k≤n⁠, the generalized k-connectivity of a graph G is defined as κk(G)=min{κG(S)|S⊆V(G) and |S|=k}⁠. The generalized k-connectivity is a generalization of traditional connectivity. In this paper, we focus on the Cayley graph generated by complete graphs and the Cayley graph generated by wheel graphs, denoted by CTn and WGn⁠, respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that κ3(CTn)=n(n−1)2−1 and κ3(WGn)=2n−3 for n≥3⁠.

Let S⊆V(G) and κG(S) denote the maximum number r of edge-disjoint trees T1,T2,…,Tr in G such that V(Ti)∩V(Tj)=S for any i,j∈{1,2,…,r} and i≠j⁠. For an integer k with 2≤k≤n⁠, the generalized k-connectivity of a graph G is defined as κk(G)=min{κG(S)|S⊆V(G) and |S|=k}⁠. The generalized k-connectivity is a generalization of the traditional connectivity. In this paper, the generalized 3-connectivity of the (n,k)-bubble-sort graph Bn,k is studied for 2≤k≤n−1⁠. We show that κ3(Bn,k)=n−2 for 2≤k≤n−1⁠, which generalizes the known result about the bubble-sort graph Bn (Li, S., Tu, J. and Yu, C. (2016) The generalized 3-connectivity of star graphs and bubble-sort graphs. Appl. Math. Comput., 274, 41–46), as the bubble-sort graph Bn is the special (n,k)-bubble-sort graph for k=n−1⁠.