Distance-edge-monitoring sets of networks

Abstract

It is important to be able to monitor the network and detect this failure when a connection (an edge) fails. For a vertex set M and an edge e of the graph G, let P(M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V(G) such that e belongs to all shortest paths between x and y. A vertex set M of the graph G is distance-edge-monitoring set if every edge e of G is monitored by some vertex of M, that is, the set P(M, e) is nonempty. The distance-edge-monitoring number of a graph G, recently introduced by Foucaud, Kao, Klasing, Miller, and Ryan, is defined as the smallest size of distance-edge-monitoring sets of G. In this paper, we determine the bounds of the distance-edge-monitoring number of grid-based pyramids and the exact value of distance-edge-monitoring number for M(t)-graph and Sierpiński-type graphs. We also compare the distance-edge-monitoring set with average degree, the size of edge set and the size of vertex set of G, where G is M(t)-graph or Sierpiński-type graphs.

1 Introduction

The networks are naturally modeled by finite undirected simple connected graphs, whose vertices represent computers and whose edges represent connections between them. It is important to be able to monitor the network and detect this failure when a connection (an edge) fails. A (hopefully) small set of vertices, called probes, of the network will be selected. At any given moment, a probe of the network can measure its graph distance to any other vertex of the network. Whenever some edge of the network fails and one of the measured distances changes, our aim is that the probes are able to detect the failure of any edge.

Probes that measure distances in graphs are present in real-life networks; for instance, this is useful in the fundamental task of routing [8, 12]. They are also frequently used for problems concerning network verification [1,2,3].

For a graph G, let V(G), E(G), |V(G)|, e(G) denote the set of vertices, the set of edges and the cardinal number of V(G) and E(G), respectively. If G is a path, then e(G) also denote the length of G. We denote d(G) the average degree of the vertices of G. Let $G-e$ denote the subgraph obtained by deleting edge e from G. Let $d_G(x,y)$ denote the distance between two vertices x and y in a graph G, without causing confusion, we can abbreviate it to d(x, y).

Definition 1

[10] For a set M of vertices and an edge e of a graph G, let P(M, e) be the set of pairs (x, y) with x a vertex of M and y a vertex of V(G) such that $d_G(x,y)\ne d_{G-e}(x,y)$. In other words, e belongs to all shortest paths between x and y in G.

Definition 2

[10] For a vertex x, let EM(x) be the set of edges e such that there exists a vertex v in G with $(x,v)\in P(\{x\},e)$.

If $e\in EM(x)$, then we say that e is monitored by x. For a given vertex set $A=\{x_{i}\,|\,1\le i\le k\}$. In this paper, we denote $EM(A)=\bigcup _{i=1}^{k}EM(x_{i})$.

Definition 3

[10] A set M of vertices of a graph G is distance-edge-monitoring set if every e of G is monitored by some vertex of M, that is, the set P(M, e) is nonempty. Equivalently, $\bigcup _{x\in M}EM(x)=E(G)$.

Definition 4

[10] The distance-edge-monitoring number ${\text {dem}}(G)$ of a graph G is defined as the smallest size of a distance-edge-monitoring set of G.

Foucaud et al. [10] showed that determining ${\text {dem}}(G)$ for an input graph G is an NP-complete problem, even for apex graphs. They also showed that ${\text {dem}}(G)$ is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number.

The pyramids network is one of the important network topologies as it has been used in both hardware architectures and software structures for parallel computing, graph theory, digital geometry, machine vision, and image processing [7, 13, 15, 16]. M(t)-graph and Sierpiński-type graphs are used in the design of interconnection networks, distributed systems, parallel algorithms, and combinatorial optimization algorithms [4, 5, 9, 11, 17, 18].

In the following sections, we study the distance-edge-monitoring numbers of grid-based pyramids, M(t)-graph and Sierpiński-type graphs. We also compare the distance-edge-monitoring set with d(G), e(G) and |V(G)|, where $G\in \{{\mathcal {S}}(n,k), \mathcal{S}\mathcal{T}(n,3), M(n)\}$.

2 Preliminary

For any subset $A\subseteq V(G)$, let G[A] be the subgraph induced by A. Let $X\subseteq V(G)$ and $Y\subseteq E(G)$. We will use $V(G)\setminus X$, $E(G)\setminus Y$ to denote the set obtained by deleting vertices of X from V(G) and the set obtained by deleting edges of Y from E(G). The edge $e=uv$ can also be represented as $e=(u,v)$. The Cartesian product of G and H is a graph, denoted as $G\Box H$, whose vertex set is $V(G)\times V(H)$. Two vertices $(u, v)^*$ and $(u',v')^*$ are adjacent precisely if $u=u'$ and $vv' \in E(H)$, or $uu'\in E(G)$ and $v=v'$. Thus, $V(G\Box H)=\{(u,v)^*\,|\, u\in V(G)~\textrm{and}~v\in V (H)\}$, $E(G\Box H)=\{((u,v)^*,(u',v')^*)\,|\,u=u',vv'\in E(H) ~\textrm{or}~uu'\in E(G),v=v'\}$. The open neighborhood N(v) of the vertex v of G is defined by $N_G(v) = \{u\in V\,|\,uv\in E\}$ and the closed neighborhood $N_G[v]$ of v by $N_G[v] = \{v\}\cup N_G(v)$. In this paper, we denote by $E_G[X,Y]$ the set of edges of G with one end in X and the other end in Y.

The $a\times b$ grid graph is the Cartesian product $P_a\Box P_b$ of path graphs on a and b vertices; here, we write it as $G_{a,b}$. Let m be a positive integer and we will use $\langle m\rangle$ to denote the set $\{0,1,2,\dots ,m\}$. Given a vertex x of a graph G and an integer i, let $L_i(x)$ denote the set of vertices at distance i of x in G.

Foucaud et al. obtained the following results.

Theorem 2.1

[10] For any integers $a,b\ge 2$, we have

$$\begin{aligned} {\text {dem}}(G_{a,b})={\text {dem}}(P_a\Box P_b)=\max \{a,b\}. \end{aligned}$$

Theorem 2.2

[10] Let x be a vertex of a connected graph G. Then, an edge uv belongs to EM(x) if and only if $u\in L_i(x)$ and v is the only neighbor of u in $L_{i-1}(x)$, for some integer i.

Theorem 2.3

[10] For positive integers n, m with $n\ge 1$ and $m\ge 3$, we have ${\text {dem}}(K_n)=n-1$ and ${\text {dem}}(C_m)=2$.

Theorem 2.4

[10] Let G be a graph and x a vertex of G. Then, for any edge e incident with x, we have $e\in EM(x)$.

3 Results for grid-based pyramid networks

A grid-based pyramid of n levels, denoted by PM(n), consists of a set of vertices $V(PM(n)) = \{(k; x, y)\,|\, 0\le k\le n, 1\le x, y\le 2^k\}$ and a set of edges $E(PM(n))=\{((k;x_1,y_1),(k;x_2,y_2))\,|\,|x_1-x_2|+|y_1-y_2|=1, 0\le k\le n, 1\le x_1,x_2, y_1, y_2\le 2^k\}\cup \{((k;x,y),(k+1;2x-1,2y-1)), ((k;x,y),(k+1;2x-1,2y)), ((k;x,y),(k+1;2x,2y-1)),((k;x,y),(k+1;2x,2y))\,|\, 0\le k\le n-1, 1\le x, y\le 2^{k-1}\}$.

Fig. 1

The graph PM(2)

If $((k; x, y),(k+1; x', y'))\in E(PM(n))$, then the vertex $u=(k; x, y)$ is said to be the parent of $u'=(k+1; x', y')$, denoted by $P(u')=u$. Conversely, $u'$ is a child of u, denoted by $C(u)=u'$. Let $P^i(u) \ (C^i(u))$ denote the i-th ancestor (descendant) of a vertex u, which is defined as follows:

(i):

$i=0,P^0(u)=u, C^0(u)=u$;

(ii):

$i=1,P^1(u)=P(u) \ (C^1(u)=C(u))$ is simply the parent (a child) of u;

(iii):

$i\ge 2,P^i(u)=P(P^{i-1}(u)) \ (C^i(u)=C(C^{i-1}(u)))$ is the parent (a child) of $P^{i-1}(u)$ $(C^{i-1}(u)$;

Let vertex set $A=\{v_i\,|\,1\le i\le n\}$, we denote $P^k(A)$ as $\bigcup _{i=1}^{n}P^k(v_i)$. The vertex $v^{0}=(0; 1, 1)$ is said to be a root of PM(n). Here, we write the subgraph at level k as $G^k$ for convenience, where $0\le k\le n$. Let $E(i\rightarrow (i+1))$ denote the set of all edges between level i and level $i+1$ and $|E(i\rightarrow (i+1))|=4^{i+1}$ where $0\le i\le n-1$. For other related properties of pyramid networks, readers can read [6, 13, 14].

Example 3.1

For $n=2$, we have $V(PM(2))=\{(0;1,1),(1;i,j),(2;p,q)\,|\,1\le i,j\le 2,1\le p,q\le 4\}$ and $E(PM(2))=\{E(G^{i})\,|\,1\le i\le 2\}\cup \{E(i\rightarrow (i+1))\,|\,0\le i\le 1\}$; see Fig. 1.

Lemma 3.1

Let G be a connected graph. For any $x\in V(G)$, if $d_G(x,u)=d_{G-uv}(x,u)$ and $d_G(x,v)=d_{G-uv}(x,v)$, then $uv\notin EM(x)$, where $uv\in E(G)$.

Proof

Since $d_G(x,u)=d_{G-uv}(x,u)$ and $d_G(x,v)=d_{G-uv}(x,v)$, it follows that there exists a shortest path $P_1$ (reps. $P_2$) from u (reps. v) to x with $uv\notin E(P_1)$ (reps. $uv\notin E(P_2)$), and hence $|e(P_1)-e(P_2)|\le 1$.

Claim 1

$uv\not \in EM(x)$.

Proof

Assume, to the contrary, that $uv\in EM(x)$. From the definition of EM(x), there exists a vertex $y\in V(G)$ such that $d_G(x,y)\ne d_{G-uv}(x,y)$, that is, uv belongs to all the shortest paths connecting x and y. We choose one such a path, say $Q_1$. Then $uv\in E(Q_1)$. Without loss of generality, suppose that $d_{Q_1}(y,u)<d_{Q_1}(y,v)$. Then, there exists a path P from x to u through $P_1$, then to y, and hence $e(P)=e(P_1)+d_{Q_1}(y,u)\le e(Q_1)=\min \{d_{Q_1}(y,u)+e(P_2),d_{Q_1}(y,v)+e(P_1)\}+1$ and $uv\notin E(P)$, contradicting to the fact that all shortest paths from x to y must contain uv. $\square$

From Claim 1, we have $uv\not \in EM(x)$, as desired. $\square$

Lemma 3.2

Let G be a connected graph. If there is only one shortest path P connecting u and v, then $E(P)\subseteq EM(u)$, where $u,v\in V(G)$.

Proof

For any edge $xy\in E(P)$ with $d_P(u,x)\ge d_P(u,y)$, if $xy\notin EM(u)$, then $d_G(u,x)=d_{G-xy}(u,x)$, it means that there exists another shortest path from u to v, a contradiction. Therefore, $xy\in EM(u)$ for any edge $xy\in E(P)$ with $d_P(u,x)\ge d_P(u,y)$. Similarly, $xy\in EM(u)$ for any edge $xy\in E(P)$ with $d_P(u,x)< d_P(u,y)$, and hence $E(P)\subseteq EM(u)$. $\square$

Lemma 3.3

Let G be a connected graph with $M\subseteq V(G)$ and $v\notin M$. For any vertex $x\in M$, if there exists a shortest path $P_{vx}$ from v to x such that $E(P_{vx})\cap E(G[M])=\emptyset$, then $E(G[M])\cap EM(v)=\emptyset$.

Proof

For any edge $xy\in E(G[M])$, there exist two shortest paths $P_{vx},P_{vy}$ from v to x and y, respectively. Since $E(P_{vx})\cap E(G[M])=\emptyset$ and $E(P_{vy})\cap E(G[M])=\emptyset$, it follows that $d_{G-xy}(v,x)=d_{G}(v,x)=e(P_{vx})$ and $d_{G-xy}(v,y)=d_{G}(v,y)=e(P_{vy})$. From Lemma 3.1, we have $E(G[M])\cap EM(v)=\emptyset$. $\square$

Observation 3.1

Let $G=PM(n)$ be pyramid network graph, and let (0; 1, 1) be a root of G, $(i;x,y)\in V(G^i) \ (1\le x,y\le 2^i)$. Then $d_G((0;1,1),(i;x,y))=i$.

Lemma 3.4

Let $t=(0;1,1)$ be the root of PM(n). For each $i \ (0\le i\le n-1)$, we have

$$\begin{aligned} E(i\rightarrow (i+1))\subseteq EM(t). \end{aligned}$$

Proof

For any $v^{i}=(i;x,y)\in V(G^i)$, where $1\le x,y\le 2^i$, we have $d_{PM(n)}(t,v^{i})=i$ for $0\le i\le n$. Then there exists only one vertex $P(v^{i})$ in $G^{i-1}$, say $P(v^{i})=(i-1;x_1,y_1)$ such that $(x,y)\in \{(2x_1,2y_1),(2x_1+1,2y_1), (2x_1,2y_1+1), (2x_1+1,2y_1+1)\}$ and $v^{i}P(v^{i})\in E(PM(n))$. Let $v^{i-1}=(i-1;x_1,y_1)$. Similarly, there exists only one vertex $P(v^{i-1})$ in $G^{i-2}$, say $P(v^{i-1})=(i-2;x_2,y_2)$ such that $(x_1,y_1)\in \{(2x_2,2y_2),(2x_2+1,2y_2),(2x_2,2y_2+1), (2x_2+1,2y_2+1)\}$ and $v^{i-1}P(v^{i-1})\in E(PM(n))$. Let $v^{i-2}=(i-2;x_2,y_2)$. Continue this process, we can find a shortest path $P=tv^1v^2\ldots v^{i-1}v^i$ from t to $v^i$, where $v^{j}\in V(G^j)$ and $1\le j\le i$.

Claim 2

P is the unique shortest path form t to $v^i$.

Proof

Assume, to the contrary, that there exists another shortest path Q from t and $v^i$. Then, there exists a vertex $w\in V(Q){\setminus } V(P)$, without loss of generality, say $w\in V(G^k) \ (1\le k\le i-1)$. Clearly, $w\ne v^k$ and hence $d(w,v^k)\ge 1$. This means that $e(Q)=d(v^i,w)+d(w,t)\ge (i-k)+1+k= i+1>e(P)$, a contradiction. $\square$

From Claim 2, P is the unique shortest path from t to $v^i$. From Lemma 3.2, $E(P)\subseteq EM(t)$, where $t\in V(G)$, and hence $E(i\rightarrow (i+1))\subseteq EM(t)$. $\square$

Lemma 3.5

Let PM(n) be a pyramid network graph. For any vertex $(n;x,y)\in V(G^n)$, where $1\le x,y \le 2^n$, we have $(\{((n;x+i,y),(n;x+i+1,y))\,|\,-2\le i\le 1\}\cup \{((n;x,y+i),(n;x,y+i+1))\,|\,-2\le i\le 1\})\cap E(G^n)\subseteq EM((n;x,y))$.

Proof

From Theorem 2.4, we have $(\{((n;x+i,y),(n;x+i+1,y))\,|\,-1\le i\le 1\}\cup \{((n;x,y+i),(n;x,y+i+1))\,|\,-1\le i\le 1\})\cap E(G^n)\subseteq EM((n;x,y))$ for any vertex $(n;x,y)\in V(G^n)$. Let $e=((n;x-2,y),(n;x-1,y))$, where $3\le x\le 2^n$ and $1\le y\le 2^n$. There exists only one shortest path $P=(n;x-2,y)(n;x-1,y)(n;x,y)$ from (n; x, y) to $(n;x-2,y)$. Thus, $d_{PM(n)}((n;x,y),(n;x-2,y))\ne d_{PM(n)-e}((n;x,y),(n;x-2,y))$, we have $e\in EM((n;x,y))$. Similarly, for any edge $e\in (\{((n;x+1,y),(n;x+2,y)),((n;x,y-2),(n;x,y-1)), ((n;x,y+1),(n;x,y+2))\})\cap E(G^n)$, we have $e\in EM((n;x,y))$. Therefore, $(\{((n;x+i,y),(n;x+i+1,y))\,|\,-2\le i\le 1\}\cup \{((n;x,y+i),(n;x,y+i+1))\,|\,-2\le i\le 1\})\cap E(G^n)\subseteq EM((n;x,y))$. $\square$

To find the upper bound of $\textrm{dem}(PM(n))$, we need to determine the distance-edge-monitoring set M of $G^n$. By Lemma 3.5, Algorithm 3.1 gives the method of finding the set M. We first divide $V(G^n)$ into $4^{n-1}$ parts $V_{i,j}=\{(2i,2j),(2i+1,2j),(2i,2j+1),(2i+1,2j+1)\}$, where $1\le i,j \le 2^{n-1}$. Then, we choose a vertex from each set $V_{i,j}$ and put them in the new set M. If $E(G^n)-EM(M)=\emptyset$, then we get the desired set M. If $E(G^n)-EM(M)\ne \emptyset$, then we choose an incident vertex of every edges of $E(G^n)-EM(M)$ and put them in set M, and hence we find the desired set M.

Algorithm 3.1

The algorithm of finding a distance-edge-monitoring set M of the grid graph $G^{n}$.

Lemma 3.6

Let PM(n) be a pyramid network graph, and

$$\begin{aligned} A&=\{(n;4(i+1),4j+1),(n;4i+2,4j+2),(n;4i+3,4j+3),\\&\quad (n;4i+1,4(j+1))\,|\,0\le i\le 2^{n-2}-1,0\le j\le \\&\quad 2^{n-2}-1\}\cup \{(n;4i+1,1),(n;1,4i+1)\,|\,0\le i\le 2^{n-2}\\&\quad -1\}\cup \{(n;4j,2^{n}),(n;2^{n},4j)\,|\,1\le j\le 2^{n-2}\}. \end{aligned}$$

For any $e\in \cup ^n_{k=1}E(G^{k})$, we have $e\in EM(A)$.

Proof

Let edge set $B=\{((n;4i+1,1),(n;4i+1,2)),((n;1,4i+1),(n;2,4i+1)), ((n;4j,2^n-1),(n;4j,2^n)),((n;2^n-1,4i+1),(n;2^n,4i+1)) \,|\,0\le i\le 2^{n-2}-1,1\le j\le 2^{n-2}\}$. By Lemma 2.4, the edges in B can be monitored by its incident vertex. Thus, we have $B\subseteq EM(\{(n;4i+1,1),(n;1,4i+1),(n;4j,2^{n}),(n;2^{n},4j) \,|\,0\le i\le 2^{n-2}-1,1\le j\le 2^{n-2}\})$ From Lemma 3.5, the vertex set $\{(n;4(i+1),4j+1),(n;4i+2,4j+2),(n;4i+3,4j+3), (n;4i+1,4(j+1))\,|\,0\le i\le 2^{n-2}-1, 0\le j\le 2^{n-2}-1\}$ can monitor edges in $E(G^n)\setminus B$. Hence, $E(G^n)\subseteq EM(A)$.

For any $e=((n-1;a,b),(n-1;a+1,b))\in E(G^{n-1})$, there exists one vertex $(n;x,y)\in A\cap (C((n-1;a-1,b))\cup C((n-1;a+2,b)))$. If $(n;x,y)\in A\cap C((n-1;a-1,b))$, then there exists only one shortest path $P=(n;x,y)(n-1;a-1,b)(n-1;a,b)(n-1;a+1,b)$ from (n; x, y) to $(n-1;a+1,b)$. Similarly, there exists a unique shortest path $P'=(n;x,y)(n-1;a-1,b)(n-1;a,b)$ from (n; x, y) to $(n-1;a,b)$. From Lemma 3.2, we have $e\in EM((n;x,y))$. If $(n;x,y)\in A\cap C((n-1;a+2,b))$, then there exists only one shortest path $Q=(n;x,y)(n-1;a+2,b)(n-1;a+1,b)$ from (n; x, y) to $(n-1;a+1,b)$. Similarly, there exists a unique shortest path $Q'=(n;x,y)(n-1;a+2,b)(n-1;a+1,b)(n-1;a-1,b)$ from (n; x, y) to $(n-1;a,b)$. From Lemma 3.2, we have $e\in EM((n;x,y))$. Therefore, $E(G^{n-1})\subseteq EM(A)$.

Let edge $e=((k;a,b),(k;a',b'))\in E(G^k)$ where $1 \le$ $k\le n-2$. Since $V(G^k)=P^{n-k}(A)$, we can find a vertex $(n;x,y)\in A\cap C^{n-k}((k;a,b))$ such that there exists only one shortest path $P=(n;x,y)P((n;x,y))$ $P^2((n;x,y))\cdots P^{n-k+1}((n;x,y))(k;a,b)$ from (n; x, y) to (k; a, b). Similarly, there exists only one shortest path $Q=(n;x,y) P((n;x,y))P^2((n;x,y))\cdots P^{n-k+1}((n;x,y))(k;a,b)$ $(k;a',b')$ from (n; x, y) to $(k;a',b')$. Therefore, $e\in EM(A)$ for any $e\in \cup ^n_{k=1}E(G^{k})$. $\square$

Lemma 3.7

Let PM(n) be a pyramid network graph. For any vertex $(i;x,y)\in V(G^i)$ where $0\le i\le n-1$ and $1\le x,y \le 2^i$, we have $E(G^n)\cap EM((i;x,y))=\emptyset$.

Proof

Let $G=PM(n)$ and $e=((n;a,b),(n;a',b'))\in E(G^n)$. There exists a shortest path from (i; x, y) to (n; a, b) (resp. $(n;a',b')$) through edge (P((n; a, b)), (n; a, b)) (resp. $(P((n;a',b')),(n;a',b'))$) that does not contain e, and thus

$$\begin{aligned}&d_{G}((i;x,y),(n;a,b))=d_{G-e}((i;x,y),(n;a,b)),\\&d_{G}((i;x,y),(n;a',b'))=d_{G-e}((i;x,y),(n;a',b')). \end{aligned}$$

By Lemma 3.1, we have $e\notin EM((i;x,y))$, and hence $E(G^n)\cap EM((i;x,y))=\emptyset$. $\square$

Theorem 3.1

Let PM(n) be a pyramid network graph. Then,

$$\begin{aligned} 2^{n}\le {\text {dem}}(PM(n))\le 4^{n-1}+2^n+1. \end{aligned}$$

Proof

Let set $A'=\{(n;4(i+1),4j+1),(n;4i+2,4j+2),(n;4i+3,4j+3), (n;4i+1,4(j+1))\,|\,1\le i\le 2^{n-2},0\le j\le 2^{n-2} \}\cup \{(n;4i+1,1),(n;1,4i+1)\,|\,0\le i\le 2^{n-2}\}\cup \{(n; 4j,2^{n}),(n;2^{n},4j)\,|\,1\le j\le 2^{n-2}\}$ and $A=A'\cup \{(0;1,1)\}$. From Lemmas 3.4 and 3.6, we have $e\in EM(A)$ for any $e\in E(PM(n))$, and hence ${\text {dem}}(PM(n))\le 4^{n-1}+2^n+1$.

To show ${\text {dem}}(PM(n))\ge 2^{n}$, by Theorem 2.1 and Lemma 3.7, we know $E(G^n)$ can only be monitored by $V(G^n)$ and ${\text {dem}}(G^n)= {\text {dem}}(G_{2^n,2^n})=2^n$. Hence we need at least $2^n$ vertices to monitor all edges of $E(G^n)$. $\square$

4 Results for M(t) networks

In this section, we introduce a family of modular, self-similar and outer-planar graphs with the small-world property. The graph M(t) [9], with vertex set $V(M(t))=\{(0,0)_i^t, (0,1)_i^t, (0,2)_i^t, (0,3)_i^t, (1,0)_i^t, (1,1)_i^t, (1,2)_i^t,(1,3)_i^t\}$, where $1\le i\le 2^{t-2}$ and $t\ge 2$, is constructed as follows:

• For $t=0$, M(0) has two vertices and an edge connecting them.

• For $t=1$, M(1) is obtained from two graphs M(0) connected by two new edges.

• For $t\ge 2$, M(t) is obtained from two graphs $M(t-1)$ by connecting them with two new edges. In each $M(t-1)$ the two vertices chosen are adjacent with maximum degree and have also been used at step $t-1$ to connect two $M(t-2)$.

For other related properties of M(t)-graph, readers can read [4, 5].

If $t=0$, then $M(0)\cong K_2$. If $t=1$, then $M(1)\cong C_4$. If $t=2$, then $M(2)\cong G_{2,4}$. Here, we call the two edges of M(t) that connect two copies of $M(t-1)$ as moving edges, as the red edges; see Fig. 2.

Fig. 2

The graph M(t)

Theorem 4.1

For integer $t\ge 0$, we have

$$\begin{aligned} {\text {dem}}(M(t))= \left\{ \begin{array}{ll} 2^{t}, &{} \textrm{if}~0\le t\le 2; \\ 2^{t-1}, &{} \textrm{if}~t\ge 3. \end{array} \right. \end{aligned}$$

We prove the above theorem by the following lemmas. From Theorems 2.1 and 2.3, we have following conclusion.

Lemma 4.1

${\text {dem}}(M(0))=1$, ${\text {dem}}(M(1))=2$ and ${\text {dem}}(M(2))=4$.

Lemma 4.2

The edges in $\{((0,0)_i^t,(1,0)_i^t)),\,|\,1\le i\le 2^{t-2},~t\ge 2\}\cup \{((0,3)_i^t,(1,3)_i^t)) \,|\,1\le i\le 2^{t-2},~t\ge 2\}$ of M(t) can only be monitored by its incident vertex.

Proof

Let $e=((0,0)_a^t,(1,0)_a^t)\in \{((0,0)_i^t,(1,0)_i^t)$ $\,|\,1\le i\le 2^{t-2}\}$ and $G=M(t)$. For $x\in V(G)$, if $x\in \{(0,0)_a^t,(1,0)_a^t\}$, then it follows from Lemma 2.4 that $e\in EM(x)$. Suppose that $x\notin \{(0,0)_a^t,(1,0)_a^t\}$. Note that there exists a 4-cycle, say $C_4=(0,0)_a^t(1,0)_a^t(1,1)_a^t(0,1)_a^t$ containing e. If there exists a shortest path from x to $(0,0)_a^t$ containing the edge e, then this shortest path contains edge $((1,1)_a^t,(1,0)_a^t)$. We can find another shortest path through edges $((1,1)_a^t,(0,1)_a^t)$ and $((0,1)_a^t,(0,0)_a^t)$, such that this path does not contain e. Obviously, the shortest path from x to $(1,0)_a^t$ does not contain e. If there exists a shortest path from x to $(1,0)_a^t$ containing the edge e, then this shortest path contains the edge $((0,1)_a^t,(0,0)_a^t)$. We can find another shortest path through edges $((0,1)_a^t,(1,1)_a^t)$ and $((1,1)_a^t,(1,0)_a^t)$, such that this path does not contain e. Furthermore, the shortest path from x to $(1,0)_a^t$ does not contain e. Thus, we have $d_{G}(x,(0,0)_a^t)=d_{G-e}(x,(0,0)_a^t)$ and $d_{G}(x,(1,0)_a^t)=d_{G-e}(x,(1,0)_a^t)$. From Lemma 3.1, we have $e\notin EM(x)$.

For $x\in V(G)$, if $x\in \{(0,3)_a^t,(1,3)_a^t\}$, then it follows from Lemma 2.4 that $e\in EM(x)$. Suppose that $x\notin \{(0,3)_a^t,(1,3)_a^t\}$. Similarly, we have $d_{G}(x,(0,3)_a^t)=d_{G-e}(x,(0,3)_a^t)$ and $d_{G}(x,(1,3)_a^t)=d_{G-e}(x,(1,3)_a^t)$. From Lemma 3.1, we have $e\notin EM(x)$.

Therefore, the edges in $\{((0,0)_i^t,(1,0)_i^t)),\,|\,1\le i\le 2^{t-2},~t\ge 2\}\cup \{((0,3)_i^t,(1,3)_i^t)) \,|\,1\le i\le 2^{t-2},~t\ge 2\}$ of M(t) can only be monitored by its incident vertex. $\square$

Observation 4.1

For $A=\{(0,0)_1^3,(1,3)_1^3,(0,0)_2^3,(1,3)_2^3\}$ $\subseteq V(M(3))$ and $x\in A$, the set EM(x) see Table 1.

Table 1 The set of EM(x)

Lemma 4.3

${\text {dem}}(M(3))=4$.

Proof

To show ${\text {dem}}(M(3))\le 4$, we choose vertex set $A=\{(0,0)_1^3,(1,3)_1^3,(0,0)_2^3,(1,3)_2^3\}$. By Observation 4.1, we have $E(M(3))\subseteq EM(A)$. From Lemma 4.2, we can see that edges $((0,0)_i^3,(1,0)_i^3)$, $((0,3)_i^3,(1,3)_i^3)$, where $1\le i\le 2$, can only be monitored by its incident vertex, and hence ${\text {dem}}(M(3))\ge 4$. $\square$

Lemma 4.4

For any step $t\ge 3$, the moving edges of M(t) can be monitored by some element in $\{(0,0)_i^t,(1,3)_i^t\,|\,1\le i\le 2^{t-2}\}$.

Proof

Let $A=\{(0,0)_i^t,(1,3)_i^t\,|\,1\le i\le 2^{n-2}\}$. For any step $t\ge 3$, there are four types of the incident vertices of moving edges, that is, $(1,1)_{i}^t$, $(1,2)_{j}^t$, $(0,1)_{k}^t$, $(0,2)_{l}^t$, where $1\le i,j,k,l\le 2^{t-2}$. For the integer $1\le i'\le 2^{n-2}$, suppose that the moving edge xy is connected to $(1,1)_{i'}^t$. Without loss of generality, let $x=(1,1)_{i'}^t$, then $d_{M(t)}((0,0)_{i'}^t,y)=3\ne d_{M(t)-e}((0,0)_{i'}^t,y)=5$, and hence $xy \in EM((0,0)_{i'}^t)$. Similarly, for the integers $1\le j,k,l\le 2^{n-2}$, if there exist moving edges incident to $(1,2)_j^t,(0,1)_k^t,(0,2)_l^t$, then it can be monitored by $(1,3)_j^t,$ $(0,0)_k^t,(1,3)_l^t$ in A, respectively. $\square$

Lemma 4.5

For $t\ge 4$, we have ${\text {dem}}(M(t))=2^{t-1}$.

Proof

To show ${\text {dem}}(M(t))\le 2^{t-1}$, we can regard M(t) as a graph with some copies of M(3) connected by the moving edges. From Lemma 4.3, $A_i=\{(0,0)_{2i-1}^t,(1,3)_{2i-1}^t,(0,0)_{2i}^t,(1,3)_{2i}^t \}$ is a distance-edge-monitor set of copies of $M_i(3)$ where $1\le i\le 2^{t-3}$. Let $B=\{(0,0)_i^t,(1,3)_i^t\,|\,1\le i\le 2^{t-2}\}$. From Lemma 4.4, the moving edges connecting the copies of M(3) can be monitored by the vertex in B. Clearly, $E(M(t))\subseteq EM(B)$, and hence ${\text {dem}}(M(t))\le 2^{t-1}$.

From Lemma 4.2, the edges $((0,0)_i^t,(1,0)_i^t)$ and $((0,3)_i^t,(1,3)_i^t)$ can only be monitored by its incident vertex, where $1\le i\le 2^{t-2}$. For any set $A\subseteq V(M(t))$ with $|A|=2^{t-1}-1$, there exists an integer $k \ (1\le k\le 2^{t-2})$ such that the edge $((0,0)_k^t,(1,0)_k^t)\notin EM(A)$ or $((0,3)_k^t,(1,3)_k^t)\notin EM(A)$, and hence ${\text {dem}}(M(t))\ge 2^{t-1}$. $\square$

5 Results for Sierpiński-type graphs

The Sierpiński graph [11, 17, 18], denoted by ${\mathcal {S}}(n,k)$, $k,n\ge 1$, $k,n\in {\mathbb {N}}$, is defined on the vertex set $\{0,1,$ $\ldots ,k-1\}^n$, two different vertices $u=(i_1,i_2,\ldots ,i_n)$ and $v=(j_1,j_2,\ldots ,j_n)$ being adjacent if and only if there exists an $h\in \{1,2,\ldots ,n\}$ such that

(i):

For any t, $t<h\Rightarrow i_t=j_t$,

(ii):

$i_h\ne j_h$,

(ii):

For any t, $t>h\Rightarrow i_t=j_h$ and $j_t=i_h$.

For Sierpiński graph ${\mathcal {S}}(n,k)$, if $n=1$, then ${\mathcal {S}}(1,k)\cong K_k$. Here, we say $((i_1,i_2,\ldots ,i_{n-1},a)$, $(j_1,j_2$, $\ldots$, $j_{n-1}$, $b))\in E({\mathcal {S}}(n,k))$ as parallel edges of $((i_1',i_2',\ldots ,i_{n-1}'$, $a),(j_1',j_2'$, $\ldots$, $j_{n-1}'$, $b))\in E({\mathcal {S}}(n,k))$. It is immediate that ${\mathcal {S}}(n,k)$ consists of k attached copies of ${\mathcal {S}}(n-1,k)$, and any two different copies are connected by a unique bridge edge. we refer to any ${\mathcal {S}}(n-1,k)$ copy of ${\mathcal {S}}(n,k)$ as ${\mathcal {S}}_i(n,k) \ (1\le i\le k)$. Obviously, ${\mathcal {S}}_i(n,k)\cong {\mathcal {S}}_j(n,k)\cong {\mathcal {S}}(n-1,k) \ (1\le i\ne j\le k)$ and $V({\mathcal {S}}_i(n,k))=\{(i,h_2,\ldots ,h_n)\,|\,0\le h_j\le k-1\}$.

Example 5.1

For integers $n=3$ and $k=3$, we have $V({\mathcal {S}}(3,3))=\{(i_1,i_2,i_3)\,|\,i_1,i_2,i_3\in \{0,1,2\} \}$ and $E({\mathcal {S}}(3,3))=\{\{(i_1,i_2,i_3),(j_1,j_2,j_3)\}\,|\, i_1\ne j_1, i_2=i_3=j_1, j_2=j_3=i_1$ or $i_1=j_1,i_2\ne j_2, i_3=j_2, j_3=i_2$ or $i_3\ne j_3, i_1=j_1, i_2=j_2 \}$. Clearly, the edges in $\{((1,0,0), (1,0,2)), ((1,0,2), (1,2,0)), ((2,1,0), (2,1,2))\}$ are the parallel edges of ((0, 1, 0), (0, 1, 2)). The graph is shown in Fig. 3.

Example 5.2

For integers $n=2$ and $k=4$, we have $V({\mathcal {S}}(2,4))=\{(i_1,i_2)\, |\, i_1,i_2\in \{0,1\}\}$ and $E({\mathcal {S}}(2,4))=\{\{(i_1,i_2),(j_1,j_2)\}\,|\, i_1\ne j_1, i_2=j_1, j_2=i_1$ or $i_1=j_1, i_2\ne j_2\}$. The graph ${\mathcal {S}}(2,4)$ is shown in Fig. 4.

From Theorem 2.3, we have following corollary.

Corollary 5.1

${\text {dem}}({\mathcal {S}}(1,k))=k-1$.

Observation 5.1

Let x be any vertex of a triangle, and let the edge e not incident to x. Then, $e\notin EM(x)$.

Fig. 3

The graph ${\mathcal {S}}(3,3)$

Observation 5.2

For Sierpiński graph ${\mathcal {S}}(3,3)$, let $P_{0\rightarrow j}$ denote the shortest path between (0, 0, 0) and (j, j, j) where $1\le j\le 2$, see Fig. 3, that is,

$$\begin{aligned} E(P_{0\rightarrow j})&=\{((0,0,0), (0,0,j)), ((0,0,j), (0,j,0)),((0,j,0),\\&\quad (0,j,j)),((0,j,j)(j,0,0)),((j,0,0),(j,0,j)),((j,\\&\quad 0,j), (j,j,0)), ((j,j,0), (j,j,j))\}. \end{aligned}$$

Let $P_{1\rightarrow 2}$ denote the shortest path between (1, 1, 1) and (2, 2, 2), that is,

$$\begin{aligned} E(P_{1\rightarrow 2})&=\{((1,1,1), (1,1,2)), ((1,1,2), (1,2,1)), ((1,2,1),\\&\quad (1,2,2)), ((1,2,2), (2,1,1)),((2,1,1), (2,1,2)),\\&\quad ((2,1,2), (2,2,1)), ((2,2,1), (2,2,2))\}. \end{aligned}$$

Then, we have the set EM((0, 0, 0)) and EM((1, 1, 1)); see Table 2.

Table 2 The set of EM(x)

Lemma 5.1

For Sierpiński graph ${\mathcal {S}}(3,3)$, we have ${\text {dem}}({\mathcal {S}}(3,3))=2$.

Proof

To show ${\text {dem}}({\mathcal {S}}(3,3))\le 2$, let $A=\{(0,0,0),$ $(1,1,1)\}$. From Observation 5.2, we have $E({\mathcal {S}}(3,3))\subseteq EM(A)$. To show ${\text {dem}}({\mathcal {S}}(3,3))\ge 2$, choosing any vertex $x\in {\mathcal {S}}(3,3)$, we can find a triangle with x as a vertex. From Observation 5.1, there is an edge e satisfying $e\notin EM(x)$. $\square$

Fig. 4

graph ${\mathcal {S}}(2,4)$

Observation 5.3

For integers $n,k\ge 1$, let $(i_{1},i_{2},\ldots ,$ $i_{n-1},j)\in V({\mathcal {S}}(n,k))$ and $A_j=E[(i_{1},i_{2},\ldots ,i_{n-1},j),$ $N_{{\mathcal {S}}(n,k)}((i_{1},i_{2},\ldots ,i_{n-1},$ j))]. where $0\le i_{1},i_{2},\ldots ,$ $i_{n-1},j\le k-1$. Then $EM((0,0,\ldots ,0,j))=A_j$.

Theorem 5.2

For integers $n,k\ge 1$, we have

$$\begin{aligned} {\text {dem}}({\mathcal {S}}(n,k))=k-1. \end{aligned}$$

Proof

If $n=1$, then it follows from Corollary 5.1 that ${\text {dem}}({\mathcal {S}}(n,k))=k-1$. Suppose that $n\ge 2$. To show ${\text {dem}}({\mathcal {S}}(n,k))\le k-1$, let $A=\{(0,0,0,\ldots ,0,j)\,|\,0\le j\le k-2\}$. From Observation 5.3, we have $E({\mathcal {S}}(n,k))\subseteq EM(A)$. To prove ${\text {dem}}({\mathcal {S}}(n,k))\ge k-1$, we choose any vertex set $B\subseteq V({\mathcal {S}}(n,k))$ with $|B|=k-2$. Since there are at most $k-2$ distinct nth coordinate of vertices in B, without loss of generality, say $B\subseteq \{(i_{1},i_{2},\ldots ,i_{n-1},j)\,|\,0\le j\le k-3\}$, it follows from Observation 5.3 that there exists at least one edge $((i_{1},i_{2},\ldots ,i_{n-1},k-2), (i_{1},i_{2},\ldots ,i_{n-1},k-1))$ which cannot be monitored by B. $\square$

The Sierpiński triangle graph [11], denoted by ST(n, k), is obtained from the Sierpiński graph S(n, k) by contracting edges that lie in no complete subgraph $K_{k}$. Clearly, for $1\le r\le n-2$ and $j\ne l,j,l\in [0,k-1]$, the two incident vertices of bridge edge $((i_1,\ldots , i_r,j,l,\ldots ,l),(i_1,\ldots , i_r,l,j,\ldots , j)\in E(S(n,k))$ contract to a vertex, here we write as $i_1\ldots i_r\{jl\}$. Specially, the two incident vertices of bridge edge $((j,l,\ldots ,l),(l,j,\ldots , j))\in E(S(n,k))$ contract to a vertex, write as $\{j, l\}$.

Example 5.3

For integers $n=3$ and $k=3$, we have $V(ST(3,3))=\{\{0,1\},\{0,2\},\{1,2\},(i,i,i), i\{0,1\},i\{0,2\}, i\{1,2\}\,|\, 0\le i\le 2\}$ and $E(ST(3,3))=\{(i\{0,1\},i\{0,2\}),(i\{0,2\},i\{1,2\}), (i\{0,1\},i\{1,2\}),((0,0,0),0\{0,1\}),((0,0,0),0\{0,2\}), ((1,1,1),1\{0,1\}),((1,1,1),1\{1,2\}), ((2,2,2),2\{0,2\}), ((2,2,2),2\{1,2\}), (\{0,1\},0\{0,1\}), (\{0,1\}, 0\{1,2\}), (\{0,1\},1\{0,1\}),(\{0,1\},1\{0,2\}),(\{0,2\},0\{0,2\}), (\{0,2\},0\{1,2\}),(\{0,2\},2\{0,1\}),(\{0,2\},2\{0,2\}), (\{1,2\},1\{0,2\}), (\{1,2\}, 1\{1,2\}),(\{1,2\},2\{0,1\}),(\{1,2\},2\{1,2\}) \,|\, i\in \{0,1,2\}\}$. The graph ST(3, 3) is shown in Fig. 5.

Observation 5.4

Let $A=\{0\{0,1\}, 0\{1,2\},1\{0,2\},$ $1\{1,2\}, 2\{0,2\}, 2\{1,2\}\}\subseteq V(ST(3,3))$. Then, we have the set EM(x), where $x\in A$; see Table 3.

Table 3 The set of EM(x)

Lemma 5.2

If $A=\{(i_1\ldots i_{n-2}\{0,1\},i_1\ldots i_{n-2}\{0,2\}),$ $(i_1\ldots i_{n-2}\{0,1\},i_1\ldots i_{n-2}\{1,2\}),(i_1\ldots i_{n-2}\{0,2\},i_1\ldots$ $i_{n-2}\{1,2\}) \,|\,i_l\in \{0,1,2\},1\le l\le n-2\}\subseteq E(ST(n,3))$, then $e\in A$ can only be monitored by its incident vertex.

Proof

Let $u=i_1\ldots i_{n-2}\{0,1\},v=i_1\ldots i_{n-2}\{1,2\}$ with $i_1=\ldots =i_{n-2}=0$, and $uv\in A$, $x\in V(ST(n,3)){\setminus } \{u,v\}\}$. If the vertex $i_1\ldots i_{n-3}\{0,1\}$ is on the shortest path P (reps. Q) from x to u (reps. v), then $uv\notin E(P)$ (reps. E(Q)) and thus

$$\begin{aligned} d_{ST(n,3)}(x,u)= & {} d_{ST(n,3)-uv}(x,u), \\ d_{ST(n,3)}(x,v)= & {} d_{ST(n,3)-uv}(x,v). \end{aligned}$$

From Lemma 3.3, we have $uv\notin EM(x)$. If $i_1\ldots$ $i_{n-3}\{0,2\}$ is on the shortest path from x to u (reps. v), then there exists a shortest path from x to u through the edges $(i_1\ldots i_{n-3}\{0,2\},i_1\ldots i_{n-2}\{0,2\})$, $(i_1\ldots i_{n-2}\{0,2\},u)$ that does not contain uv, and there also exists a shortest path from x to v through the edge $(i_1\ldots i_{n-3}\{0,2\},v)$ that does not contain uv, hence

$$\begin{aligned} d_{ST(n,3)}(x,u)= & {} d_{ST(n,3)-uv}(x,u), \\ d_{ST(n,3)}(x,v)= & {} d_{ST(n,3)-uv}(x,v). \end{aligned}$$

By Lemma 3.1, we have $uv \notin EM(x)$.

If $(0,0,\ldots ,0)$ is on the shortest path from x to u (reps. v), then there exists a shortest path from x to u through the edges $((0,0,\ldots ,0),u)$ that does not contain uv, and there also exists a shortest path from x to v through the edges $((0,0,\ldots ,0),i_1\ldots i_{n-2}\{0,2\})$, $(i_1\ldots i_{n-2}\{0,2\},v)$ that does not contain uv, hence

$$\begin{aligned} d_{ST(n,3)}(x,u)= & {} d_{ST(n,3)-uv}(x,u), \\ d_{ST(n,3)}(x,v)= & {} d_{ST(n,3)-uv}(x,v). \end{aligned}$$

By Lemma 3.1, we have edge $uv \notin EM(x)$. Otherwise, $x=i_1\ldots i_{n-2}\{1,2\}$. Clearly, we also have $uv \notin EM(i_1\ldots i_{n-2}\{1,2\})$. Similarly, we have the same conclusion for $e'\in A\setminus \{uv\}$, as desired. $\square$

Fig. 5

The graph ST(3, 3)

Observation 5.5

${\text {dem}}(ST(2,3))=3$.

Lemma 5.3

${\text {dem}}(ST(3,3))=6$.

Proof

To show ${\text {dem}}(ST(3,3))\le 6$, let $A=\{0\{0,1\},0\{1,2\}$, $1\{0,2\},1\{1,2\}$, $2\{0,2\},2\{1,2\}\}$. From Observation 5.4, we have $E(ST(3,3))\subseteq EM(A)$. To prove ${\text {dem}}(ST(3,3))\ge 6$, by Lemma 5.2, we need at least 6 vertices to monitor the edges in $\{(i\{0,1\},i\{0,2\})$, $(i\{0,1\},i\{1,2\})$, $(i\{0,2\},i\{1,2\})\,|\,0\le i\le 2\}$. $\square$

Theorem 5.3

For integer $n\ge 2$, we have

$$\begin{aligned} {\text {dem}}(ST(n,3))= \left\{ \begin{array}{ll} 3, &{} \textrm{if}~n=2; \\ 2\cdot 3^{n-2}, &{} \textrm{if}~n\ge 3. \end{array} \right. \end{aligned}$$

Proof

For $n=2$, by Observation 5.5, we have ${\text {dem}}(ST(2,3))=3$. Suppose that $n\ge 3$. To show ${\text {dem}}(ST(n,3))\le 2\cdot 3^{n-2}$, let $A=\{i_1\ldots i_{n-3}0\{0,1\}$, $i_1\ldots i_{n-3}$ $i'_{n-2}\{0,2\}$, $i_1\ldots i_{n-2}$ $\{1,2\}$ $\,|\,i'_{n-2}\in \{1,2\}$, $i_l\in \{0,1,2\}$, $1\le l\le n-2\}$. Clearly, Sierpiński triangle graph ST(n, 3) consists of $3^{n-3}$ attached copies of ST(3, 3). For every copy of $ST_i(3,3) \ (1\le i\le 3^{n-2})$, $E(ST_i(3,3))$ can be monitored by $A\cap V(ST_i(3,3))$ with $|A\cap V(ST(3,3))|=6$. To prove ${\text {dem}}(ST(n,3))\ge 2\cdot 3^{n-2}$, by Lemma 5.2, the edges in $\{(i_1\ldots i_{n-2}\{0,1\}$, $i_1\ldots i_{n-2}\{0,2\}),(i_1\ldots i_{n-2}\{0,1\}$, $i_1\ldots i_{n-2}\{1,2\}),(i_1\ldots i_{n-2}\{0,2\}$, $i_1\ldots i_{n-2}\{1,2\})\,|\,i_l$ $\in \{0,1,2\}$, $1\le l\le n-2\}$ can only be monitored by its incident vertex, hence ${\text {dem}}(ST(n,3))\ge 2\cdot 3^{n-2}$. $\square$

6 Conclusion

In the end, we compare the distance-edge-monitoring set with d(G), e(G), |V(G)| when $n\rightarrow \infty$, where $G\in \{{\mathcal {S}}(n,k), \mathcal{S}\mathcal{T}(n,3), M(n)\}$. Let z(G), x(G) and y(G) be defined as follows,

$$\begin{aligned} z(G)= & {} \lim _{n\rightarrow \infty }\textrm{dem}(G)/d(G); \\ x(G)= & {} \lim _{n\rightarrow \infty }\textrm{dem}(G)/|V(G)|; \\ y(G)= & {} \lim _{n\rightarrow \infty }\textrm{dem}(G)/e(G). \end{aligned}$$

We know that $e(M(n))=2^n+2^{n-1}-2$, $V(M(n))=2^{n+1}$, $\textrm{dem}(M(n))=2^{n-1}$; $e({\mathcal {S}}(n,k)))=\frac{k^{n+1}-k}{2}$, $V({\mathcal {S}}(n,k))=k^n$, $\textrm{dem}({\mathcal {S}}(n,k))=k-1$; $e(\mathcal{S}\mathcal{T}(n,3)))=3^n$, $V(\mathcal{S}\mathcal{T}(n,3))=\frac{3^n+3}{2}$, $\textrm{dem}(\mathcal{S}\mathcal{T}(n,3))=2\cdot 3^{n-2}$. The values of z(G), x(G) and y(G), where $G\in \{{\mathcal {S}}(n,k), \mathcal{S}\mathcal{T}(n,3), M(t)\}$, which show that the relation among $\textrm{dem}(G)$, z(G), x(G) and y(G) is related to the structure of the graph G; see Table 4.

Table 4 The values of z(G), x(G) and y(G), where $G\in \{{\mathcal {S}}(n,k), \mathcal{S}\mathcal{T}(n,3), M(t)\}$