The Generalized 3-Edge-Connectivity of Lexicographic Product Graphs

Abstract

The generalized $k$-edge-connectivity $\lambda _k(G)$ of a graph $G$ is a natural generalization of the concept of edge-connectivity. The generalized edge-connectivity has many applications in networks. The lexicographic product of two graphs $G$ and $H$, denoted by $G\circ H$, is an important method to construct large graphs from small ones. In this paper, we mainly study the generalized 3-edge-connectivity of $G \circ H$, and get lower and upper bounds of $\lambda _3(G \circ H)$. An example is given to show that all bounds are sharp.

Supported by NSFC No. 11371205 and PCSIRT.

1 Introduction

All graphs considered in this paper are simple, finite and undirected. We follow the terminology and notation of Bondy and Murty [3]. For a graph $G$, the local edge-connectivity between two distinct vertices $u$ and $v$, denoted by $\lambda (u,v)$, is the maximum number of pairwise edge-disjoint $uv$-paths. A nontrivial graph $G$ is $k$-$edge$-$connected$ if $\lambda (u,v)\ge k$ for any two distinct vertices $u$ and $v$ of $G$. The edge-connectivity $\lambda (G)$ of a graph $G$ is the maximum value of $k$ for which $G$ is $k$-edge-connected.

Naturally, the concept of edge-connectivity can be extended to a new concept, the generalized $k$-edge-connectivity, which was introduced by Li et al. [22]. For a graph $G=(V,E)$ and a set $S\subseteq V$ of at least two vertices, a Steiner tree connecting $S$ (or simply, an $S$ -tree) is a such subgraph $T=(V',E')$ of $G$ that is a tree with $S\subseteq V'$. Two $S$-trees $T$ and $T'$ are said to be edge-disjoint if $E(T)\cap E(T')=\emptyset$. The generalized local edge-connectivity $\lambda (S)$ is the maximum number of pairwise edge-disjoint Steiner trees connecting $S$. For an integer $k$ with $2\le k\le n$, the generalized $k$ -edge-connectivity $\lambda _k(G)$ of $G$ is defined as $\lambda _k(G)=\min \{\lambda (S)\,|\, S\subseteq V(G), |S|=k\}$. Obviously, $\lambda _2(G)=\lambda (G)$. Set $\lambda _k(G)=0$ if $G$ is disconnected. Similarly, the concept of the generalized $k$-connectivity was introduced by Hager in [11] and it is also studied in [5]. We refer to [17–19, 22, 24, 30] for some known results of the generalized connectivity and edge-connectivity.

The generalized edge-connectivity has a close relation to an important problem, the Steiner tree packing problem, which asks for finding a set of maximum number of edge-disjoint $S$-trees in a given graph $G$ where $S\subseteq V(G)$, see [9, 31]. An extreme of Steiner tree packing problem is the Spanning tree packing problem where $S=V(G)$. For any graph $G$, the spanning tree packing number or $STP$ number, is the maximum number of edge-disjoint spanning trees contained in $G$. For the $STP$ number, we refer to [1, 25, 26]. The difference between the Steiner tree packing problem and the generalized edge-connectivity is as follows: the former problem studies local properties of graphs since $S$ is given beforehand, while the latter problem focuses on global properties of graphs since $S$ runs over all $k$-subsets of $V(G)$.

The generalized edge-connectivity and the Steiner tree packing problem have applications in $VLSI$ circuit design, see [9, 27]. In this application, a Steiner tree is needed to share an electronic signal by a set of terminal nodes. A Steiner tree is also used in computer communication networks and optical wireless communication networks, see [6, 7]. Another application arises in the Internet Domain. Suppose that a given graph $G$ represents a network. We select arbitrary $k$ vertices as nodes. Suppose one of the nodes in $G$ is a broadcaster and all other nodes are users. The broadcaster wants to broadcast as many streams of movies as possible, so that the users have the maximum number of choices. Each stream of movie is broadcasted via a tree connecting all the users and the broadcaster. So, in essence we need to find the maximum number of Steiner trees connecting all the users and the broadcaster, namely, we want to get $\lambda (S)$, where $S$ is the selected $k$ nodes. Clearly, it is a Steiner tree packing problem. Furthermore, if we want to know whether for any $k$ nodes the network $G$ has above properties, then we need to compute $\lambda _k(G)=\min \{\lambda (S)\}$ in order to prescribe the reliability and the security of the network.

From a theoretical perspective, both extremes of the generalized edge-connectivity problem are fundamental theorems in combinatorics. One extreme is when we have two terminals. In this case edge-disjoint trees are just edge-disjoint paths between the two terminals, and so the problem becomes the well-known edge version of Menger theorem. The other extreme is when all the vertices are terminals. In this case edge-disjoint trees are just spanning trees of the graph, and the problem becomes the classical Nash-Williams-Tutte theorem, see [23, 29].

Graph product is an important method to construct large graphs from small ones. So it has many applications in the design and analysis of networks, see [9, 14, 15]. The lexicographic product (or composition), Cartesian product, strong product and the direct product are the main four standard products of graphs. More information about the (edge-) connectivity of these four product graphs can be found in [4, 8, 10, 12, 13, 16, 32]. The generalized 3-edge-connectivity of Cartesian product graphs was studied and the lower bound is given in [28]. In this paper, we study the generalized 3-edge-connectivity of lexicographic product graphs and provide both sharp lower and upper bounds.

Theorem 1

Let $G$ and $H$ be two non-trivial graphs such that $G$ is connected. Then $\lambda _3(H)+\lambda _3(G)|V(H)|\le \lambda _3(G\circ H) \le \min \Big \{\Big \lfloor \frac{4\lambda _3(G)+2}{3}\Big \rfloor |V(H)|^2,\delta (H)+\delta (G)|V(H)|\Big \}$. Moreover, the lower and upper bounds are sharp.

Note that the vertex version, the generalized 3-connectivity of Cartesian product and lexicographic product graphs, was studied in [16, 20]. The results there are quite different from ours.

2 Preliminary and Notation

Let $G=(V,E)$ be a graph and $S$ be an $s$-subset of $V$. $G[S]$ denotes the induced subgraph of $G$ on $S$ and $\mathcal {E}^{|S|}$ denotes the empty graph on $S$, that is, the union of $s$ isolated vertices. Connect x to S is to join $x$ to each vertex of $S$ for a vertex $x$ outside $S$. Given two sets $X$, $Y$ of vertices, we call a path $P$ an $XY$-$path$ if the end-vertices of $P$ are in $X$ and $Y$, respectively, and all inner vertices are in neither $X$ nor $Y$. If $u$ and $v$ are two vertices on a path $P$, $uPv$ will denote the segment of $P$ from $u$ to $v$. Two distinct paths are edge-disjoint if they have no edges in common; internally disjoint if they have no internal vertices in common; vertex-disjoint if they have no vertices in common. For $X=\{x_1,x_2,\cdots ,x_k\}$ and $Y=\{y_1,y_2,\cdots ,y_k\}$, an $XY$-$linkage$ is defined as a set $Q$ of $k$ vertex-disjoint $XY$-paths $x_iP_iy_i$, $1\le i\le k$.

Let $G=(V_1,E_1)$ and $H=(V_2,E_2)$. The lexicographic product (or composition) $G\circ H$ of $G$ and $H$ is defined as follows: $V(G\circ H)=V_1\times V_2$, two vertices $(u,v)$ and $(u',v')$ are adjacent if and only if either $uu'\in E_1$ or $u=u'$, $vv'\in E_2$. In other words, $G\circ H$ is obtained by substituting a copy $H(u)$ of $H$ for every vertex $u$ of $G$ and joining each vertex of $H(u)$ with every vertex of $H(u')$ if $uu'\in E_1$. The vertex set $G(v)=\{(u,v)|u\in V_1\}$ for some fixed vertex $v$ of $H$ is called a layer of graph $G$ or simply a $G$-$layer$. Analogously, we define the $H$-$layer$ with respect to a vertex $u$ of $G$ and denote it by $H(u)$. It is not hard to see that any $G$-$layer$ induces a subgraph of $G\circ H$ that is isomorphic to $G$ and any $H$-$layer$ induces a subgraph of $G\circ H$ that is isomorphic to $H$. For any $u,u'\in V(G)$ and $v,v'\in V(H)$, $(u,v),(u,v')\in V(H(u))$, $(u',v),(u',v')\in V(H(u'))$, $(u,v),(u',v)\in V(G(v))$, $(u,v'),(u',v')\in V(G(v'))$. We view $(u,v')$ and $(u',v)$ as $the~vertices~corresponding~to$ $(u,v)$ in $G(v')$ and $H(u')$, respectively. Similarly, we can define the path and tree corresponding to some path and tree, respectively. The edge $(u,v)$ $(u',v')$ is called a $first$-$type$ edge if $uu'\in E_1$ and $v=v'$; a $second$-$type$ edge if $vv'\in E_2$ and $u=u'$; a $third$-$type$ edge if $uu'\in E_1$ and $v\ne v'$. For a subset $W$ of $V(G)$ with $W=\{u_1,\cdots ,u_t\}$, we denote $H(W)=H(u_1)\cup \cdots \cup H(u_t)$. We use $K_W$ to denote a subgraph of $G\circ H$, where $V(K_W)=V(G[W]\circ H)$, $E(K_W)=E(G[W]\circ H)\setminus E(H(W))$, namely, the end-vertices of an edge of $K_W$ are in different $H$-layers.

Unlike the other products, the lexicographic product does not satisfy the commutative law, that is, $G\circ H$ could not be isomorphic to $H\circ G$. By a simple observation, $G\circ H$ is connected if and only if $G$ is connected. Moreover, $\delta (G\circ H)=\delta (G)|V(H)|+\delta (H)$.

Let $G=(V,E)$ be a connected graph, $S=\{x,y,z\}\subseteq V$, and $T$ be an $S$-tree. We call $T$ a $type~I$ S-tree if it is just a path whose end-vertices belong to $S$; a $type~{II}$ S-tree if it has exactly three leaves $x$, $y$, $z$. Note that each vertex in a type $I$ S-tree has degree two except the two end-vertices in $S$. If $T$ is of type ${II}$, every vertex in $T\setminus S$ has degree two except one vertex of degree three. By deleting some vertices and edges of an S-tree $T$, it is easy to check that $T$ is of type $I$ or ${II}$. Because our aim is to get as many $S$-trees as possible, in this paper, each $S$-tree is of type $I$ or ${II}$. Therefore, we get the following proposition.

Proposition 1

Let $G=(V,E)$ be a graph with $\lambda _3(G)=k\ge 2$, $S=\{x,y,z\}\subseteq V$. Then there exist $k-2$ edge-disjoint $S$-trees $T_1,\cdots ,T_{k-2}$ such that $E(T_i)\cap E(G[S])=\emptyset$ where $1\le i\le k-2$.

Proof

By the definition of an $S$-tree, we know that $|E(T_i)\cap E(G[S])|\le 2$ and $|\{T_i\,|\,E(T_i)\cap E(G[S])\ne \emptyset \}|\le 3$. Let $T_1,\cdots ,T_k$ be $k$ edge-disjoint $S$-trees. If $|\{T_i\,|\,E(T_i)\cap E(G[S])\ne \emptyset \}|\le 2$, we are done. Thus, it remains to consider the case when $G[S]$ is a triangle. Without loss of generality, assume that $|\{T_i\,|\,E(T_i)\cap E(G[S])\ne \emptyset \}|=3$ and $E(T_i)\cap E(G[S])\ne \emptyset$, where $i=1,2,3$. Then $T_1$, $T_2$, $T_3$ have the structures $F_1$ or $F_2$ shown in Fig. 1. Furthermore, we can obtain $T'_1$, $T'_2$, $T'_3$ from $T_1$, $T_2$, $T_3$ such that $E(T'_1)\cap E(G[S])=\emptyset$. See figures $F'_1$ and $F'_2$ in Fig. 1, where the $S$-tree $T'_1$ is shown by gray lines. Thus $T'_1,T_4,\cdots ,T_k$ are our desired $k-2$ edge-disjoint $S$-trees.

Fig. 1.

Three $S$-trees of type $I$.

Li et al. [21, 22] got the following results which will be useful for our proof.

Observation 1

[22] For any graph $G$ of order $n$, $\lambda _k(G)\le \lambda (G)$. Moreover, the upper bound is tight.

Observation 2

[22] If G is a connected graph, then $\lambda _k(G)\le \delta (G)$. Moreover, the upper bound is tight.

Proposition 2

[21] Let $G$ be a connected graph of order $n$ with minimum degree $\delta$. If there are two adjacent vertices of degree $\delta$, then $\lambda _k(G)\le \delta -1$ for $3\le k\le n$. Moreover, the upper bound is sharp.

From Proposition 2, it is easy to get the following observation.

Observation 3

Let $G$ be a connected graph with $\lambda _3(G)=k$, and $x$, $y$ be two adjacent vertices of $G$. Then $d_G(x)\ge k+1$ or $d_G(y)\ge k+1$.

Example 1

Let $G$ be a path of length two and $H$ be a complete graph of order four, and $T_1$, $T_2$ be two edge-disjoint $S$-trees in $H$, where $S=\{x,y,z\}\subseteq V(H)$. The structure of $G\circ (T_1\cup T_2)$ is shown as $F_a$ in Fig. 2, where the edges of a complete bipartite graph is simplified by bold black crossing edges. Note that $E(G\circ T_1)\cap E(G\circ T_2)=E(G\circ \mathcal {E}^{|S|})$.

Fig. 2.

The structures of $G\circ (T_1\cup T_2)$ and $(T_1\cup T_2)\circ H$.

Remark 1

Two edge-disjoint $S$-trees $T_1$, $T_2$ in $H$ may have other vertices in common except $S$. If $V(T_1)\cap V(T_2)=W$, then $E(G\circ T_1)\cap E(G\circ T_2)=E(G\circ \mathcal {E}^{|W|})$.

Example 2

Let $G$ be a complete graph of order four and $H$ be an arbitrary graph, and $T_1$, $T_2$ be two edge-disjoint $S$-trees in $G$, where $S=\{x,y,z\}\subseteq V(G)$. The structure of $(T_1\cup T_2)\circ H$ is shown as $F_b$ in Fig. 2 and $E(T_1\circ H)\cap E(T_2\circ H)=E(H(S))$.

Remark 2

Two edge-disjoint $S$-trees $T_1$, $T_2$ in $G$ may have other vertices in common except $S$. If $V(T_1)\cap V(T_2)=W$, then $E(T_1\circ H)\cap E(T_2\circ H)=E(H(W))$.

3 Lower Bound of $\lambda _3(G\circ H)$

In this section, we mainly prove the following theorem.

Theorem 2

Let $G$ and $H$ be two non-trivial graphs such that $G$ is connected. Then $\lambda _3(G\circ H)\ge \lambda _3(H)+\lambda _3(G)|V(H)|$. Moreover, the lower bound is sharp.

By the following corollary, we know that the bound of the above theorem is sharp.

Corollary 1

$\lambda _3(P_s\circ P_t)=t+1$.

Proof

By Theorem 2, $\lambda _3(P_s\circ P_t)\ge t+1$. On the other hand, by Observation 2, $\lambda _3(P_s\circ P_t)\le \delta (P_s\circ P_t)=t+1$. Thus $\lambda _3(P_s\circ P_t)=t+1$.

Let $G$ be a graph with $V(G)=\{u_1,u_2,\cdots ,u_{n_1}\}$ and $\lambda _3(G)=r_1$, and let $H$ be a graph with $V(H)=\{v_1,v_2,\cdots ,v_{n_2}\}$ and $\lambda _3(H)=r_2$. Set $S=\{x,y,z\}\subseteq V(G\circ H)$. Firstly, we give the sketch of the proof of Theorem 2. In total, the desired $r_2+r_1n_2$ $S$-trees are obtained on two stages: $r_2$ edge-disjoint $S$-trees by first-type and second-type edges on Stage $I$ and $r_1n_2$ edge-disjoint $S$-trees by the remaining first-type edges and the third-type edges on Stage ${II}$. Note that if $H$ is disconnected, then $\lambda _3(H)=0$ as defined, thus we omit Stage $I$ immediately. Next we shall prove Theorem 2 by a series of lemmas according to the position of $x$, $y$, $z$ in $G\circ H$.

Lemma 1

If $x,y,z$ belong to the same $H$-layer, then there exist $r_2+r_1n_2$ edge-disjoint $S$-trees.

Proof

Without loss of generality, assume that $x,y,z\in H(u_1)$, $x=(u_1,v_1)$, $y=(u_1,v_2)$ and $z=(u_1,v_3)$. On Stage $I$, since $\lambda _3(H)=r_2$, there are $r_2$ edge-disjoint $S$-trees in $H(u_1)$. On Stage ${II}$, by Observation 2, $u_1$ has $r_1$ neighbors in $G$, say $\beta _1,\beta _2,\cdots ,\beta _{r_1}$. Thus $T^*_{ij}=x(\beta _{i},v_j)\cup y(\beta _{i},v_j)\cup z(\beta _{i},v_j)$ ($1\le i\le r_1$ and $1\le j\le n_2$) are $r_1n_2$ $S$-trees. These $r_2+r_1n_2$ $S$-trees are obviously edge-disjoint, as desired.

Lemma 2

If exactly two of $x,y$ and $z$ belong to the same $H$-layer, then there exist $r_2+r_1n_2$ edge-disjoint $S$-trees.

Proof

Assume that $x,y\in H(u_1)$, $z\in H(u_2)$. Let $x''$ and $y''$ be the vertices in $H(u_2)$ corresponding to $x$ and $y$, and $z'$ be the vertex in $H(u_1)$ corresponding to $z$, respectively. Consider the following two cases.

Case 1.   $z'\in \{x,y\}$.

Without loss of generality, assume that $z'=x$, $x=(u_1,v_1)$, $y=(u_1,v_2)$ and $z=(u_2,v_1)$.

By Observation 1, there are $r_2$ edge-disjoint $v_1v_2$-paths $P_1,P_2,\cdots , P_{r_2}$ in $H$ such that $\ell (P_1)\le \ell (P_2)\le \cdots \le \ell (P_{r_2})$. Denote the neighbor of $v_1$ in $P_i$ by $\alpha _i$ ($1\le i\le r_2$). Set $D=\{\alpha _1,\alpha _2,\cdots , \alpha _{r_2}\}$. Notice that $\alpha _p\ne \alpha _q$ if $p\ne q$. Similarly, there are $r_1$ edge-disjoint $u_1u_2$-paths $Q_1,Q_2,\cdots , Q_{r_1}$ in $G$ such that $\ell (Q_1)\le \ell (Q_2)\le \cdots \le \ell (Q_{r_1})$. For each $i$ with $1\le i\le r_1$, set $Q_i=u_1\beta _{i,1}\beta _{i,2}\cdots \beta _{i,t_i-1}u_2$ and $\ell (Q_i)=t_i$. Also, note that $\beta _{p,1}\ne \beta _{q,1}$ if $p\ne q$.

On Stage $I$, the desired $r_2$ $S$-trees are obtained associated with the longest $u_1u_2$-path $Q_{r_1}$. If $v_1$ and $v_2$ are nonadjacent in $H$, then $T^*_i=P_i(u_1)\cup Q_{r_1}(\alpha _i)\cup z(u_2,\alpha _i)$ ($1\le i\le r_2$) are $r_2$ $S$-trees as shown in Fig. 3($a$), where $P_i(u_1)$ is the path in $H(u_1)$ corresponding to $P_i$ in $H$, and $Q_{r_1}(\alpha _i)$ is the path in $G(\alpha _i)$ corresponding to $Q_{r_1}$ in $G$. Now $v_1$ and $v_2$ are adjacent in $H$, that is, $P_1=v_1v_2$ and $(u_1,\alpha _1)=y$. It follows from Observation 3 that $d_{H}(v_1)\ge r_2+1$ or $d_{H}(v_2)\ge r_2+1$, without loss of generality, say $d_{H}(v_1)\ge r_2+1$. For $P_1$, $T^*_1=xy\cup x(u_1,\alpha _{r_2+1})\cup Q_{r_1}(\alpha _{r_2+1})\cup z(u_2,\alpha _{r_2+1})$ is an $S$-tree, where $\alpha _{r_2+1}\notin D$, $\alpha _{r_2+1}$ is a neighbor of $v_1$ in $H$, and $Q_{r_1}(\alpha _{r_2+1})$ is the path in $G(\alpha _{r_2+1})$ corresponding to $Q_{r_1}$, see Fig. 3($b$). For $P_i$ ($2\le i\le r_2$), set $T^*_i=P_i(u_1)\cup Q_{r_1}(\alpha _i)\cup z(u_2,\alpha _i)$. It is easy to see that these $r_2$ $S$-trees are edge-disjoint. The case that $d_{H}(v_2)\ge r_2+1$ can be proved similarly.

Fig. 3.

The $r_2$ edge-disjoint $S$-trees where the edges of an $S$-tree are shown by the same type of lines.

Up to now, we should remark that the first-type edges incident with $x$ and $y$ in $G\circ H$ are not used whether or not $v_1$ and $v_2$ are adjacent in $H$. Since a vertex in $V(H)\setminus \{v_1,v_2\}$ may belong to more than one $v_1v_2$-path, we make use of either the $r_2$ neighbors of $v_1$ or the $r_2$ neighbors of $v_2$ to get our desired $r_2$ edge-disjoint $S$-trees.

Define a new graph $(G\circ H)^*$ from $G\circ H$ by deleting the edges of $r_2$ $S$-trees on Stage $I$. On Stage ${II}$, with the aid of $Q_i$ ($1\le i\le r_1$), we successively construct $r_1n_2$ $S$-trees in $(G\circ H)^*$ in non-decreasing order of the length of $Q_i$. We distinguish two subcases by the length $t_1$ of $Q_1$.

Subcase 1.1.  $t_1\ge 2$.

Recall that $Q_1=u_1\beta _{1,1}\beta _{1,2}\cdots \beta _{1,t_1-1}u_2$. We will obtain $n_2$ internally disjoint $xy$-paths $A_1,A_2,\cdots , A_{n_2}$ in $K_{u_1,\beta _{1,1}}$, and a $V(H(\beta _{1,1}))V(H(\beta _{1,t_1-1}))$-linkage $B_1,B_2,\cdots , B_{n_2}$ by third-type edges associated with $\beta _{1,1}Q_1\beta _{1,t_1-1}$. Thus, $T^*_i=A_i\cup B_i\cup (\beta _{1,t_1-1},v_i)z$ are $n_2$ edge-disjoint $S$-trees, where the subscript $i$ $(1\le i\le n_2)$ of $v_i$ is expressed module $n_2$ as one of $1,2,\cdots ,n_2$. Indeed, this can be done. Set $A_i=x(\beta _{1,1},v_i)y$ for $1\le i\le n_2$. If $t_1=2$, then $B_i=\emptyset$. If $t_1\ge 3$, then $B_i=(\beta _{1,1},v_i)(\beta _{1,2},v_{i+1})(\beta _{1,3},v_i)(\beta _{1,4},v_{i+1})\cdots (\beta _{1,t_1-1},v_i)$ and $T^*_i=A_i\cup B_i\cup (\beta _{1,t_1-1},v_i)z$ when $t_1$ is even; $B_i=(\beta _{1,1},v_i)(\beta _{1,2},v_{i+1})(\beta _{1,3},v_i)(\beta _{1,4},v_{i+1})\cdots (\beta _{1,t_1-1},v_{i+1})$ and $T^*_i=A_i\cup B_i\cup (\beta _{1,t_1-1},v_{i+1})z$ when $t_1$ is odd. For example, let $n_2=4$. Then 4 edge-disjoint $S$-trees are shown in Fig. 4 when $t_1=2$, $t_1=3$ and $t_1=4$, respectively.

Fig. 4.

The $4$ edge-disjoint $S$-trees where the edges of an $S$-tree are shown by the same type of lines.

Subcase 1.2.   $t_1=1$ and $Q_1=u_1u_2$.

Since $\lambda _3(G)=r_1$, it follows from Observation 3 that $d_{G}(u_1)\ge r_1+1$ or $d_{G}(u_2)\ge r_1+1$.

If $d_{G}(u_1)\ge r_1+1$, then denote another neighbor of $u_1$ in $G$ by $\beta _{r_1+1,1}$ except $u_2$ and $\beta _{i,1}$ ($2\le i\le r_1$). We obtain $n_2$ edge-disjoint $S$-trees associated with $Q_1$ as follows. Let $T^*_1=(\beta _{r_1+1,1},v_1)x\cup (\beta _{r_1+1,1},v_1)y\cup xz$, $T^*_2=(\beta _{r_1+1,1},v_2)x\cup (\beta _{r_1+1,1},v_2)y\cup yz$, $T^*_i=(u_2,v_i)x\cup (u_2,v_i)y\cup (u_2,v_i)(u_1,v_{i+1})\cup (u_1,v_{i+1})z$ for $3\le i\le n_2-1$, $T^*_{n_2}=(u_2,v_{n_2})x\cup (u_2,v_{n_2})y\cup (u_2,v_{n_2})(u_1,v_3)\cup (u_1,v_3)z$; see Fig. 5($a$).

Fig. 5.

The $n_2$ edge-disjoint $S$-trees where the edges of an $S$-tree are shown by the same type of lines.

If $d_{G}(u_2)\ge r_1+1$, then denote another neighbor of $u_2$ in $G$ by $\gamma _{r_1+1}$ except $u_1$ and $\beta _{i,t_i-1}$ ($2\le i\le r_1$). For $Q_1$, set $T^*_1=xz\cup zy$, $T^*_2=xy''\cup y''y\cup (\gamma _{r_1+1},v_1)y''\cup (\gamma _{r_1+1},v_1)z$, $T^*_i=(u_2,v_i)x\cup (u_2,v_i)y\cup (u_2,v_i)(u_1,v_{i+1})\cup (u_1,v_{i+1})z$ for $3\le i\le n_2-1$, and $T^*_{n_2}=(u_2,v_{n_2})x\cup (u_2,v_{n_2})y\cup (u_2,v_{n_2})(u_1,v_3)\cup (u_1,v_3)z$; see Fig. 5($b$).

In both subcases, similar to Subcase 1.1, we are able to get $n_2$ edge-disjoint $S$-trees associated with $Q_i$ ($2\le i\le r_1$), it follows that $n_2r_1$ edge-disjoint $S$-trees are obtained, as desired.

Case 2.   $z'\notin \{x,y\}$.

Assume that $x=(u_1,v_1)$, $y=(u_1,v_2)$ and $z=(u_2,v_3)$. Let $S'=\{v_1,v_2,v_3\}$ and $S''=\{x,y,z'\}$.

By Observation 1, there are $r_1$ edge-disjoint $u_1u_2$-paths $Q_1,Q_2,\cdots , Q_{r_1}$ in $G$ such that $\ell (Q_1)\le \ell (Q_2)\le \cdots \le \ell (Q_{r_1})$. By Proposition 1, $r_2$ edge-disjoint $S'$-trees $T_1,T_2,\cdots , T_{r_2}$ exist in $H$ such that $0\le |\{T_i|E(T_i)\cap E(H[S'])\}|\le 2$. Suppose $E(T_i)\cap E(H[S'])=\emptyset$ for $3\le i\le r_2$. According to whether $T_1$ and $T_2$ share edges with $E(H[S'])$ or not, we get the desired $S$-trees in the following subcases.

Subcase 2.1. $E(T_1)\cap E(H[S'])=\emptyset$ and $E(T_2)\cap E(H[S'])=\emptyset$.

Denote the neighbor of $v_3$ in $T_i$ by $\alpha _i$ where $1\le i\le r_2$. On Stage $I$, let $T^*_i=T_i(u_1)\cup Q_{r_1}(\alpha _i)\cup z(u_2,\alpha _i)$, where $T_i(u_1)$ is the tree in $H(u_1)$ corresponding to $T_i$, $Q_{r_1}(\alpha _i)$ is the path in $G(\alpha _i)$ corresponding to $Q_{r_1}$ for $1\le i\le r_2$. On Stage ${II}$, if $\ell (Q_1)\ge 2$, then construct $n_2$ $S$-trees similar to Case 1; if $\ell (Q_1)=1$, then either $u_1$ or $u_2$ has a neighbor which is not in each $u_1u_2$-path $Q_i$ in $G$. Thus $n_2$ $S$-trees associated with $Q_1$ are shown in Fig. 6 ($u_1$ has another neighbor in $G$ in Fig. 6($a$) and $u_2$ has another neighbor in $G$ in Fig. 6($b$)). Similar to Case 1, we obtain $n_2$ $S$-trees associated with $Q_i$ for $2\le i\le r_1$, thus there exist $r_2+r_1n_2$ edge-disjoint $S$-trees, as desired.

Fig. 6.

The $n_2$ edge-disjoint $S$-trees where the edges of an $S$-tree are shown by the same type of lines.

Subcase 2.2. $E(T_1)\cap E(H[S'])\ne \emptyset$ and $E(T_2)\cap E(H[S'])=\emptyset$.

Suppose $|E(T_1)\cap E(H[S'])|=1$ and $E(T_2)\cap E(H[S'])=\emptyset$. Furthermore, suppose $E(T_1)\cap E(H[S'])=v_1v_2$ and $d_{T_1}(v_2)=2$ (the other possibilities can be proved similarly). For $1\le i\le r_2$, denote the neighbor of $v_3$ in $T_i$ by $\alpha _i$. Then we are able to obtain $r_2$ $S$-trees with the aid of $\alpha _i$ on Stage $I$ and $r_1n_2$ $S$-trees on Stage ${II}$ similar to Subcase 2.1. It remains to consider the case that $|E(T_1)\cap E(H[S'])|=2$ and $E(T_2)\cap E(H[S'])=\emptyset$. On Stage $I$, if $d_{Q_{r_1}}(u_1,u_2)\ge 2$ and $d_{T_1}(v_2)=2$ or $d_{Q_{r_1}}(u_1,u_2)\ge 2$ and $d_{T_1}(v_3)=2$, then an $S$-tree $T^*_1$ associated with $T_1$ has the structure as shown in Fig. 7, where $\bar{x}$ is the neighbor of $x''$ in $Q_{r_1}(v_1)$; if $d_{Q_{r_1}}(u_1,u_2)=1$, then $T^*_1=xyy''z$ (when $u_1$ has another neighbor outside $Q_i$) or $T^*_1=xyz'z$ (when $u_2$ has another neighbor outside $Q_i$). We obtain other $r_2+r_1n_2-1$ $S$-trees similar to Subcase 2.1. Thus there exist $r_2+r_1n_2$ edge-disjoint $S$-trees, as desired.

Fig. 7.

The solid lines stand for the edges of the $S$-tree.

Subcase 2.3. $E(T_1)\cap E(H[S'])\ne \emptyset$ and $E(T_2)\cap E(H[S'])\ne \emptyset$.

Without loss of generality, suppose $|E(T_2)\cap E(H[S'])|=1$. If $|E(T_1)\cap E(H[S'])|=1$, then assume that the two $S'$-trees $T_1$ and $T_2$ have the structure as one of $F_3,F_4,F_5,F_6$ in Fig. 8, where $v_2$ is marked. For $1\le i\le r_2$, denote the neighbor of $v_2$ in $T_i\setminus \{v_1,v_3\}$ by $\alpha _i$ and construct $r_2+r_1n_2$ $S$-trees similar to Subcase 2.1. So $|E(T_1)\cap E(H[S'])|=2$, and then $T_1$ and $T_2$ have the structure $F_7$, where $T_1$ is shown in Fig. 8 by dotted lines. For $2\le i\le r_2$, denote the neighbor of $v_2$ in $T_i\setminus \{v_1,v_3\}$ by $\alpha _i$. Construct an $S$-tree $T^*_1$ similar to Subcase 2.2 and other $r_2+r_1n_2-1$ $S$-trees similar to Subcase 2.1. Thus, there exist $r_2+r_1n_2$ edge-disjoint $S$-trees, as desired.

Fig. 8.

Two $S'$-trees of type $I$.

Lemma 3

If $x,y,z$ belong to distinct $H$-layers, then there exist $r_2+r_1n_2$ edge-disjoint $S$-trees.

Proof

Assume that $x\in H(u_1)$, $y\in H(u_2)$ and $z\in H(u_3)$. Let $y'$, $z'$ be the vertex corresponding to $y$, $z$ in $H(u_1)$, $x''$, $z''$ be the vertex corresponding to $x$, $z$ in $H(u_2)$, and $x'''$, $y'''$ be the vertex corresponding to $x$, $y$ in $H(u_3)$, respectively. We distinguish the following three cases.

Case 1.   $x$, $y$, $z$ belong to the same $G$-layer.

We may assume that $x=(u_1,v_1)$, $y=(u_2,v_1)$, $z=(u_3,v_1)$. It is easily seen that there are $r_2$ neighbors of $v_1$ in $H$, say $\alpha _1,\alpha _2,\cdots ,\alpha _{r_2}$, and $r_1$ edge-disjoint $\{u_1,u_2,u_3\}$-trees $T_1,T_2,\cdots , T_{r_1}$ in $G$. For a tree $T_i$ in $G$, set by $T_i(\alpha _j)$ the corresponding tree in $G(\alpha _j)$ for $1\le i\le r_1$, $1\le j\le r_2$.

On Stage $I$, $T_j^{*}=T_1(\alpha _j)\cup x(u_1,\alpha _j)\cup y(u_2,\alpha _j)\cup z(u_3,\alpha _j)$ ($1\le j\le r_2$) are $r_2$ edge-disjoint $S$-trees.

On Stage ${II}$, if $T_j$ is of type $I$ for some $j$ with $1\le j\le r_1$, then we may assume that $d_{T_j}(u_2)=2$. Denote the neighbor of $u_1$, $u_3$ in $T_j$ by $\eta _{j}$, $\gamma _{j}$ and the neighbors of $u_2$ by $\beta _{j}$, $\bar{\beta _{j}}$ ($\beta _{j}$ is nearer to $u_1$ than $\bar{\beta _{j}}$), where $\beta _{j}$, $\eta _{j}$ and $\bar{\beta _{j}}$, $\gamma _{j}$ may be the same vertex. Associated with $u_1T_ju_2$ and $u_2T_ju_3$, there are $n_2$ edge-disjoint $xy$-paths $A=\{A_1,\cdots ,A_{n_2}\}$ and edge-disjoint $yz$-paths $B=\{B_1,\cdots ,B_{n_2}\}$, respectively. Then $T^*_{ij}=A_i\cup B_i$ ($1\le i\le {n_2}$) are $n_2$ edge-disjoint $S$-trees. Indeed, this can be done. We will only provide the construction of $A$ according to $d_{T_j}(u_1,u_2)$, since the construction of $B$ is similar to that of $A$. If $d_{T_j}(u_1,u_2)=1$, then set $A_1=xy$, $A_i=x(u_2,v_i)(u_1,v_{i+1})y$ for $2\le i\le n_2-1$, and $A_{n_2}=x(u_2,v_{n_2})(u_1,v_2)y$; if $d_{T_j}(u_1,u_2)=2$, then set $A_i=x(\eta _{j},v_i)y$ for $1\le i\le n_2$. It remains to consider the case that $d_{T_j}(u_1,u_2)\ge 3$. Since there is a $V(H(\eta _{j}))V(H(\beta _{j}))$-linkage $D_1,D_2,\cdots , D_{n_2}$ by third-type edges of $G\circ H$ associated with $\eta _{j}T_j\beta _{j}$, it follows that $A_i=x(\eta _{j},v_i)\cup D_i\cup (\beta _{j},v_i)y$, where the subscript $i$ $(1\le i\le n_2)$ of $v_i$ is expressed module $n_2$ as one of $1,2,\cdots ,n_2$. It remains to consider the case that $T_j$ is of type ${II}$. Denote the neighbor of $u_1$, $u_2$, $u_3$ in $T_j$ by $\eta _{j}$, $\beta _{j}$, $\gamma _{j}$ and the only one three-degree vertex in $T_j$ by $w_j$ ($\eta _{j}$, $\beta _{j}$, $\gamma _{j}$ and $w_j$ may be the same vertex). We find a $V(H(\eta _{j}))V(H(\beta _{j}))$-linkage and a $V(H(\gamma _{j}))V(H(w_j))$-linkage respectively by third-type edges of $G\circ H$, and connect $x$, $y$, $z$ respectively to $V(H(\eta _{j}))$, $V(H(\beta _{j}))$ and $V(H(\gamma _{j}))$. Thus, $n_2$ edge-disjoint $S$-trees are obtained associated with $T_j$. Since $1\le j\le r_1$, it follows that $r_1{n_2}$ edge-disjoint $S$-trees are obtained on Stage ${II}$, as desired.

Case 2.   Exactly two of $x$, $y$, $z$ belong to the same $G$-layer.

We only consider the case $x=y'$ (the other cases $x=z'$ or $y'=z'$ can be proved by similar arguments). Assume that $x=(u_1,v_1)$, $y=(u_2,v_1)$ and $z=(u_3,v_2)$. Since $\lambda _3(H)=r_2$, there exist $r_2$ edge-disjoint $v_1v_2$-paths $P_1,P_2,\cdots , P_{r_2}$ in $H$ such that $\ell (P_1)\le \ell (P_2)\le \cdots \le \ell (P_{r_2})$. For $1\le i\le r_2$, denote the neighbor of $v_1$ and $v_2$ in $P_i$ by $\alpha _i$ and $\beta _i$, respectively, and denote by $P_i(u_3)$ in $H(u_3)$ corresponding to $P_i$. Since $\lambda _3(G)=r_1$, there are $r_1$ edge-disjoint $\{u_1,u_2,u_3\}$-trees $T_1,T_2,\cdots , T_{r_1}$ in $G$.

On Stage $I$, if $\ell (P_1)\ge 2$, then set $T_i^{*}=x(u_1,\alpha _{i})\cup y(u_2,\alpha _{i})\cup zP_i(u_3)(u_3,\alpha _{i}) \cup T_1(\alpha _{i})$ for $1\le i\le r_2$. Otherwise, $\ell (P_1)=1$, that is, $v_1$ is adjacent to $v_2$. Then $d_{H}(v_1)\ge r_2+1$ or $d_{H}(v_2)\ge r_2+1$. If $d_{H}(v_1)\ge r_2+1$, then $T_1^{*}=\{x(u_1,\alpha _{r_2+1}), y(u_2,\alpha _{r_2+1}), zx''', x'''(u_3,\alpha _{r_2+1})\} \cup T_1(\alpha _{r_2+1})$, where $\alpha _{r_2+1}$ is another neighbor of $v_1$ except $\alpha _i$ ($1\le i\le r_2$). If $d_{H}(v_2)\ge r_2+1$, then $T_1^{*}=\{xz',z'(u_1,\beta _{r_2+1}), yz'',z''(u_2,\beta _{r_2+1}), z(u_3,\beta _{r_2+1})\}\cup T_1(\beta _{r_2+1})$, where $\beta _{r_2+1}$ is another neighbor of $v_1$ except $\beta _i$ ($1\le i\le r_2$).

By similar arguments as in Case 1 of Lemma 3, $r_1n_2$ edge-disjoint $S$-trees can be obtained on Stage ${II}$.

Case 3.   $x$, $y$, $z$ belong to different $G$-layers.

Assume that $x=(u_1,v_1)$, $y=(u_2,v_2)$ and $z=(u_3,v_3)$. Let $S'=\{v_1,v_2,v_3\}$ and $S''=\{u_1,u_2,u_3\}$.

Since $\lambda _3(H)=r_2$, there are $r_2$ edge-disjoint $S'$-trees $T_1,T_2,\cdots , T_{r_2}$ in $H$. For $1\le i\le r_2$, denote by $\alpha _i$ the vertex in $T_i$ adjacent to a vertex in $S'$, say $v_1$, and $\ell (T_i)$ denotes the size of $T_i$. Similarly, there are $r_1$ edge-disjoint $S''$-trees $T_1',T_2',\cdots , T_{r_1}'$ in $G$.

On Stage $I$, if $\ell (T_i)\ge 3$ for each $i$ with $1\le i\le r_2$, then let $T_i^{*}=x(u_1,\alpha _{i})\cup yT_i(u_2)(u_2,\alpha _{i})\cup zT_i(u_3)(u_3,\alpha _{i})\cup T'_1(\alpha _{i})$. Otherwise, similar to Case 2 of Lemma 2, the most difficult case is that there is an $S'$-tree of size two. Suppose $\ell (T_1)=2$ and $d_{T_1}(v_2)=2$. Thus $T_1^{*}$ has three structures as shown in Fig. 9 where $T'_1$ is of type ${II}$ in Fig. 9($a$), $T'_1$ is of type $I$ and $d_{T'_1}(u_1)=2$ in Fig. 9($b$) and $T'_1$ is of type $I$ and $d_{T'_1}(u_1)=1$ in Fig. 9($c$).

Fig. 9.

The $S$-tree with the aid of $T'_1$ shown by the solid lines.

On Stage ${II}$, $r_1n_2$ edge-disjoint $S$-trees are obtained by similar arguments as in Case 1 of Lemma 3.

In each case, we obtain $r_2+r_1n_2$ $S$-trees, and it is easily seen that these $S$-trees are edge-disjoint, as desired.

From the above three lemmas, Theorem 2 follows immediately.

4 Upper Bound of $\lambda _3(G\circ H)$

In this section, we give an upper bound of the generalized 3-edge-connectivity of the lexicographic product of two graphs.

Yang and Xu [33] investigated the classical edge-connectivity of the lexicographic product of two graphs.

Theorem 3

[33] Let $G$ and $H$ be two non-trivial graphs such that $G$ is connected. Then

$$\lambda (G\circ H)=\min \{\lambda (G)|V(H)|^2,\delta (H)+\delta (G)|V(H)|\}.$$

In [22], the sharp lower bound of the generalized 3-edge-connectivity of a graph is given as follows.

Proposition 3

[22] Let $G$ be a connected graph with $n$ vertices. For every two integers $s$ and $r$ with $s\ge 0$ and $r\in \{0,1,2,3\}$, if $\lambda (G)=4s+r$, then $\lambda _3(G)\ge 3s+\lceil \frac{r}{2}\rceil$. Moreover, the lower bound is sharp. We simply write $\lambda _3(G)\ge \frac{3\lambda (G)-2}{4}$.

From the above two results, we get the following upper bound of $\lambda _3(G\circ H)$.

Theorem 4

Let $G$ and $H$ be two non-trivial graphs such that $G$ is connected. Then

$$ \lambda _3(G\circ H)\le \min \Big \{\Big \lfloor \frac{4\lambda _3(G)+2}{3}\Big \rfloor |V(H)|^2,\delta (H)+\delta (G)|V(H)|\Big \}. $$

Moreover, the upper bound is sharp.

Proof

By Proposition 3, $\lambda (G)\le \lfloor \frac{4\lambda _3(G)+2}{3}\rfloor$. By Proposition 1 and Theorem 3, we have $\lambda _3(G\circ H)\le \lambda (G\circ H)=\min \{\lambda (G)|V(H)|^2,\delta (H)+\delta (G)|V(H)|\}$. It follows that $\lambda _3(G\circ H)\le \min \Big \{\Big \lfloor \frac{4\lambda _3(G)+2}{3}\Big \rfloor |V(H)|^2,\delta (H)+\delta (G)|V(H)|\Big \}$. Moreover, the example in Corollary 1 shows that the upper bound is sharp.