# Optimal Graphs in the Enhanced Mesh Networks

Authors: Muhammad Shahzad Akhtar; Muhammad Imran; Syed Ahtsham ul Haq Bokhary
Journal: Journal of Mathematics
 (2020)

---

## Abstract

The degree diameter problem explores the biggest graph (in terms of number of nodes) subject to some restrictions on the valency and the diameter of the graph. The restriction on the valency of the graph does not impose any condition on the number of edges (apart from taking the graph simple), so the resulting graph may be thought of as being embedded in the complete graph. In a generality of the said problem, the graph is taken to be embedded in any connected host graph. In this article, host graph is considered as the enhanced mesh network constructed from the grid network. This article provides some exact values for the said problem and also gives some bounds for the optimal graphs.


---

## Body

## 1. Introduction

All graphs discussed in paper are simple, finite, and undirected. The valencyor degree of a node or vertex in the graph G is the number of edges connected with that node in G. The maximal valency of the graph G is indicated by ΔG. The distance between two nodes u and v of G is the length of the shortest path between them. The distance between a node x and the set A is defined as dx,A=mina∈Adx,a. For any A⊆VG, let G−A denote the subgraph of G after removing from G all the nodes of A and all the edges incident to at least one node of A. The diameter of the graph G is designated by D and is described as the largest distance between any pair of nodes of the graph G. For a given graph G and natural numbers Δ and D, NGΔ,D indicates the number of nodes of largest subgraph of G with given maximal valency Δ and given diameter D.The topology of a network such as a telecommunications, multiprocessor, or local area network is generally represented by a graph such that stations or processors are represented by vertices (or nodes) and the links or the connection between these networks are represented by edges. There are many important features in the designing of such networks. One of the important aspects is to put limitation on vertex degree and its diameter. These two parameters in networks are interpreted as follows. By the degree of a node, it is meant to have the number of connections attached to that node; on the contrary, the diameter shows the largest number of links that must be required to transmit a message between any two nodes. The natural question that arises in this case is“What is then the largest number of nodes in a network with a limited degree and diameter?” If we design the network so that there is no directed edge, then this leads to the Degree/Diameter Problem. More formally, we define it as follows.Find the largest possible number of verticesNΔ,D in a graph of maximum degree Δ and diameter D.For a thorough survey of the state of the problem, see [1, 2]. In the Degree Diameter Problem, only restriction that is imposed on the edges is the maximum degree, so there is considerable freedom in placing edges so as to avoid violating the diameter constraint. In this way, the resulting graph may be thought of as being embedded in the complete graph. In this case, the complete graph is acting as the host graph.A generalization of the Degree Diameter Problem is to consider the graph as embedded in some host graph, not necessarily the complete graph. This problem becomes more interesting when the host graph is considered as a graph obtained from some network. The problem was first posed by Dekker et al.[7] in the following form.Given connected undirected host graphG, an upper bound Δ for the maximum degree, and an upper bound D for the diameter find the largest connected subgraph of maximum degree ≤Δ and diameter ≤D.In [3–6], the degree diameter problem of honeycomb network, triangular network, oxide network, and silicate network has been explored. In [7], the largest subgraph NGΔ,D has been determined with multidimensional hexagonal grid as the host graph. In [8–15], some extremal properties of graph networks are discussed. Mesh networks can relay messages using either a flooding technique or a routing technique. With routing, the message is propagated along a path by hopping from node to node until it reaches its destination. To ensure that all its paths are available, the network must allow for continuous connections and must reconfigure itself around broken paths, using self-healing algorithms such as Shortest Path Bridging. Self-healing allows a routing-based network to operate when a node breaks down or when a connection becomes unreliable. As a result, the network is typically quite reliable as there is often more than one path between a source and a destination in the network. Although mostly used in wireless situations, this concept can also apply to wired networks and to software interaction. In this work, we have extended this study to the enhanced mesh network.The Cartesian productS□T of the graphs S and T is the graph with node set VS×VT, where two nodes x1,y1 and x2,y2 are adjacent if and only if either x1=x2 and y1y2∈ET or y1=y2 and x1x2∈ES.LetPm and Pn are two paths having nodes m and n, respectively. The graph of the grid network Pm□Pn is obtained by their Cartesian product. The grid graph network Pm□Pn has mn nodes and 2mn−m−n edges. The graph of the two-dimensional infinite grid network is denoted by P∞□P∞.LetGm,n be the graph of the enhanced mesh obtained from Pm□Pn by replacing its each 4−cycle by a wheel W5, the hub of the wheel being a new vertex (see Figure 1). In the graph Gm,n, each 4-cycle of Pm□Pn is divided into four triangles where every node lie on some triangle.Figure 1
Construction of the enhanced mesh from grid graph. (a)P5□P6. (b) G5,6.
(a)
(b)Let us define the edges of the wheelW5 as follows:(i)
The edge connected to the hub and left-end vertex of upper horizontal edge inW5 is called upper-left hub edge(ii)
The edge connected to the hub and right-end vertex of upper horizontal edge inW5 is called upper-right hub edge(iii)
The edge connected to the hub and left-end vertex of lower horizontal edge inW5 is called lower-left hub edge(iv)
The edge connected to the hub and right-end vertex of lower horizontal edge inW5 is called lower-right hub edgeSincePm□Pn has m−1n−1 squares (4-cycles). Therefore, Gm,n has mn+m−1n−1=2mn−m−n+1 nodes. In Gm,n, the edges adjacent to the hub vertex in each W5 are disjoint; therefore, Gm,n has 2mn−m−n+4m−1n−1=6mn−5m−5n+4 edges. Furthermore, we define that any two wheel graphs W5 in G are said to be adjacent if they share an edge.


## 2. Methodology

In this paper, we have calculatedNGΔ,D in the infinite enhanced mesh network. First, we find the induced closed balls GD of diameter D for Δ=8 whose order is NG8,D for D≥2. The order of GD is the upper bound for NGΔ,D. We find NGΔ,D for Δ≤7 by deleting minimum number of vertices of GD. The rest of the paper is ordered as follows. In Section 3, we consider the case for Δ=8; in Section 4, the case for Δ=1,2,3,4,5,6,7 is discussed.


## 3. Result and Discussion

In this section, the results obtained are discussed. The largest subgraphs are obtained for the enhanced mesh networks for given degree and diameter.


### 3.1. Largest Subgraphs forΔ=8

LetG denote the infinite Enhanced Mesh Network in the Cartesian plane with ΔG=8.Proposition 1.
ForD≥2, let the induced subgraph of G of diameter D and maximal degree 8 is denoted by GD. Then, for k∈ℕ,(1)VGD=2k+12,forD=2k,4k2+8k+2,forD=2k+1.Proof.
For even diameterD, let GD be a closed ball having radius D/2 with center as an eight degree node n of G with node set x∈VG:dGx,n≤D/2. To find the nodes of GD, we draw horizontal lines on the nodes of GD and count the nodes on these horizontal lines by adding them from top to bottom.
Thus, forD=2k, k∈ℕ, we have(2)VGD=1+2+3+⋯+2k−2+2k−1+2k+2k+1+2k+2k−1+2k−2+⋯+3+2+1=2k+12.
Now, for odd diameterD, let GD be a closed ball having radius D−1/2 and center as the fixed triangle T with node set x∈VG:dGx,T≤D−1/2.
Then, by counting the nodes on horizontal lines, we have forD=2k+1, k∈ℕ,(3)VGD=2+3+4+⋯+2k−1+2k+2k+1+2k+2+2k+1+2k+2k−1+⋯+4+3+2=4k2+8k+2.
In Figure2, the graphs GD for D=8,9,10, and 11 are depicted. The central vertex n of GD for even D is depicted by • and for odd diameter D, the nodes of central triangle T of GD are indicated by a,b,andc and is depicted by •. It is important to note that the distance of any node x from T is defined as dx,T=miny∈VTdx,y, where the node y is the nearest node of T from x.
LetLD be the biggest connected subgraph of G with maximal degree Δ=8.
Then, forD=1, LD is the triangle K3; thus, NG8,1=3.
ForD=2k+r,wherek∈ℕandr∈0,1, the biggest subgraph LD of G with Δ=8 is the closed ball GD itself. Thus, NG8,D=VGD, for D=2k+r,k∈ℕ,r∈0,1.
Hence, we showed the following statement.Figure 2
The graph ofGD for D=8,9,10, and 11 and Δ=8.
(a)
(b)
(c)
(d)Theorem 1.
LetG be the graph of enhanced mesh and D be a positive integer. Then,(4)NG8,D=VLD=VGD,forD=2k+r,k∈ℕ,r∈0,1.
Note that the values in the abovementioned theorem are also trivial upper bounds onNGΔ,D for Δ≤7. Thus, we prove the following corollary.Corollary 1.
LetLD be the biggest connected subgraph of G of maximal degree 8. Let ΔandD be positive integers with Δ≤8. Then,(5)NGΔ,D≤LD.


## 3.1. Largest Subgraphs forΔ=8

LetG denote the infinite Enhanced Mesh Network in the Cartesian plane with ΔG=8.Proposition 1.
ForD≥2, let the induced subgraph of G of diameter D and maximal degree 8 is denoted by GD. Then, for k∈ℕ,(1)VGD=2k+12,forD=2k,4k2+8k+2,forD=2k+1.Proof.
For even diameterD, let GD be a closed ball having radius D/2 with center as an eight degree node n of G with node set x∈VG:dGx,n≤D/2. To find the nodes of GD, we draw horizontal lines on the nodes of GD and count the nodes on these horizontal lines by adding them from top to bottom.
Thus, forD=2k, k∈ℕ, we have(2)VGD=1+2+3+⋯+2k−2+2k−1+2k+2k+1+2k+2k−1+2k−2+⋯+3+2+1=2k+12.
Now, for odd diameterD, let GD be a closed ball having radius D−1/2 and center as the fixed triangle T with node set x∈VG:dGx,T≤D−1/2.
Then, by counting the nodes on horizontal lines, we have forD=2k+1, k∈ℕ,(3)VGD=2+3+4+⋯+2k−1+2k+2k+1+2k+2+2k+1+2k+2k−1+⋯+4+3+2=4k2+8k+2.
In Figure2, the graphs GD for D=8,9,10, and 11 are depicted. The central vertex n of GD for even D is depicted by • and for odd diameter D, the nodes of central triangle T of GD are indicated by a,b,andc and is depicted by •. It is important to note that the distance of any node x from T is defined as dx,T=miny∈VTdx,y, where the node y is the nearest node of T from x.
LetLD be the biggest connected subgraph of G with maximal degree Δ=8.
Then, forD=1, LD is the triangle K3; thus, NG8,1=3.
ForD=2k+r,wherek∈ℕandr∈0,1, the biggest subgraph LD of G with Δ=8 is the closed ball GD itself. Thus, NG8,D=VGD, for D=2k+r,k∈ℕ,r∈0,1.
Hence, we showed the following statement.Figure 2
The graph ofGD for D=8,9,10, and 11 and Δ=8.
(a)
(b)
(c)
(d)Theorem 1.
LetG be the graph of enhanced mesh and D be a positive integer. Then,(4)NG8,D=VLD=VGD,forD=2k+r,k∈ℕ,r∈0,1.
Note that the values in the abovementioned theorem are also trivial upper bounds onNGΔ,D for Δ≤7. Thus, we prove the following corollary.Corollary 1.
LetLD be the biggest connected subgraph of G of maximal degree 8. Let ΔandD be positive integers with Δ≤8. Then,(5)NGΔ,D≤LD.


## 4. Largest Subgraphs forΔ≤7

We are interested to find the biggest subgraph ofG with given maximal valency Δ and diameter D. Since ΔG=8, it makes perception to consider the cases for Δ≤8. For Δ=8, NGΔ,D=LD. Now, we consider the other cases.


### 4.1. Values forΔ=1,2

IfΔ=1, then the biggest connected subgraph of G is just an edge and hence NG1,D=K2.Now, we discuss the case whenΔ=2.Theorem 2.
LetG be the enhanced mesh network, and let D be a natural number. Then,(6)NG2,D=2D,whenD≥2.Proof.
ForD=2k,k∈ℕ. Let L and M be the horizontal and vertical lines, respectively, that are passing through the central node n of LD and divide the graph LD into four regions (upper left, upper right, lower left, and lower right), as shown in Figure 3. Consider a border cycle C of the lower-left region containing the central node (see the blue cycle in Figure 3(a)). Cycle C has 2D nodes.
ForD=2k+1,k∈ℕ. Let Q be the horizontal line passing through the edge bc and R be the vertical line passing through the node c of the triangle T in the graph LD that divide the graph LD into four regions (upper left, upper right, lower left, and lower right), as shown in Figure 3. Consider a border cycle C of the lower-left region containing the edge bc(see the blue cycle in Figure 3(b)). The cycle C has 2D nodes.Figure 3
The biggest subgraphLD for D=2,4,5,6,7 and Δ=2.
(a)
(b)


### 4.2. Values forΔ=7

Theorem 3.
LetD be an even natural number, and let G be an infinite enhanced mesh network. Then,(7)NG7,D=8,forD=2,NG7,D=VLD,forD=2k,k∈ℕ−1.Proof.
ForD=2, the graph contains K1,7, which is the biggest subgraph of G of valency 7, since in the graph LD (shown in Figure 3(a)) of maximal valency Δ=8, the central node can be attached to at most 7 nodes. Hence, NG7,2=8.
ForD=2k,k∈2,3,4,…, and Δ=7, we construct a subgraph MD (shown in Figure 4) from LD as follows.
LetL be the central horizontal line passing through the central node n, M be the upper neighboring row, and N be the lower neighboring row. Let H be the wheel graph W5 of LD lying on and above the central line at a distance zero on the right side of the central node n. Furthermore, suppose that x is the hub node of H:(i)
Delete the upper-left and upper-right hub edges in eachW5 lying on and above the line L of LD(ii)
Delete the lower-left and lower-right hub edges in eachW5 lying on and below the line L of LD(iii)
Delete the lower-left hub edge (lower-right hub edge) on left of the central noden(on the right of the central node n) in each W5 lying between the horizontal lines L and M of LD, except the wheel graph H whose lower-left hub edge is deleted(iv)
Delete the upper-left hub edge (upper-right hub edge) on left of the central noden(on right of the central node n) in each W5 lying between the lines L and N of the graph LD
The resulting subgraph is denoted byMD (shown in Figure 4, for D=4,6,8,10) which is the spanning subgraph of LD; hence, VLD=VMD. Furthermore, graph MD also has diameter D since the distance of all the nodes of MD from n is the same as in LD except the node x. However, dx,n=2≤D/2, for all D≥4. This implies that MD is the biggest subgraph of G of maximal valency Δ=7 and diameter D.Figure 4
M
D for D=4,6,8,10 and maximal valency Δ=7.Theorem 4.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(8)NG7,1=3,NG7,D=VLD,forD=2k+1,k∈ℕ.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 7. Hence, NG7,1=3.
ForD=2k+1,k∈ℕ, andΔ=7, we construct a subgraph QD (shown in Figure 5) from LD as follows.
LetL be the horizontal line passing through edge bc of the central triangle T of graph LD and M be the upper neighboring horizontal row. Let K be the wheel subgraph of LD containing the central triangle T:(i)
Delete the upper-left and upper-right hub edges in eachW5 lying on and above the line M of LD(ii)
Delete the lower-left and lower-right hub edges in eachW5 lying on and below the line L of LD(iii)
Delete the upper-left, lower-left hub edges in eachW5 lying on the left of wheel graph K.(iv)
Delete the upper-right and lower-right hub edges in eachW5 lying on the right of wheel graph K(v)
Furthermore, delete the left and right vertical edges in the wheel graphK
The resulting subgraph is denoted byQD (shown in Figure 5 for D=5,7,9,11) is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD. This implies that QD is the biggest subgraph of G of maximal valency Δ=7 and diameter D.Figure 5
The biggest subgraphs ofG for D=3,5,7,9,11 and Δ=7.


### 4.3. Values forΔ=6

Theorem 5.
LetD be an even natural number, and let G be the infinite enhanced mesh network. Then,(9)NG6,D=7,forD=2,NG6,D=VLD,forD=2k,k∈ℕ−1.Proof.
ForD=2, the graph contains K1,6. This is a biggest subgraph of G of maximal valency 6 since in the graph LD (shown in Figure 3(a)) of maximal valency Δ=8, and the central node can be connected to at most 6 nodes. Hence, NG6,2=7.
ForD=2k,k∈2,3,4,…, Δ=6, we construct a subgraph MD (shown in Figure 6) from LD as follows.
LetL and M be the horizontal and vertical lines passing through the central node n that divide LD into four regions (upper left, upper right, lower left, and lower right). Let H and K be the wheel graphs W5 of LD lying in the upper-right and lower-left regions at a distance 0 from the central node n. Furthermore, suppose that x and y be the hub vertices of H and K, respectively:(i)
Delete the upper-left, upper-right, and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-left, upper-right, and lower-right hub edges in eachW5 lying in the upper-right region of LD except the wheel graph H(iii)
Delete the lower-left, lower-right, and upper-left hub edges in eachW5 lying in the lower-left region of LD except the wheel graph K(iv)
Delete the lower-left, lower-right, and upper-right hub edges in eachW5 lying in the lower-right region of LD(v)
Furthermore, delete the upper-left, upper-right, lower-left hub edges, and right vertical edge inH; also, delete the lower-left, lower-right, upper-right hub edges, and left vertical edge in K
The resulting subgraph is denoted byMD (shown in Figure 6, for D=4,6,8,10), which is the spanning subgraph of LD; hence, VLD=VMD. Furthermore, the graph MD also has diameter D since the distance of all the nodes of MD from n is the same as in LD except the nodes x and y. However, dx,n=2≤D/2,dy,n=2≤D/2, for all D≥4. This implies that MD is the biggest subgraph of G of maximal valency Δ=6 and diameter D.Figure 6
M
D for D=4,6,8,10 and maximal valency Δ=6.Theorem 6.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(10)NG6,1=3,NG6,3=13,NG6,D=VLD,forD=2k+1,k∈ℕ.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 6. Hence, NG6,1=3.
ForD=3, the graph LD of maximal valency 8 is a closed ball of radius 3 (shown Figure 3(b)). For maximal valency Δ=6, the biggest subgraph cannot contain all the nodes of the graph LD, otherwise D=4. Thus, the graph shown in Figure 7(a) is the biggest subgraph of maximal valency Δ=6. Hence, NG6,3=13.
ForD=2k+1,k∈ℕ, and Δ=6, we construct a subgraph QD(shown in Figure 7) from LD as follows.
LetS be the wheel graph W5 that contains the central triangle T. Let R be the horizontal row of the wheel graphs W5 containing the wheel graph S. Let S1S2 be the wheel graphs lying on left (right) of S and is adjacent to it. Also, let S3 be the wheel graph W5 below the wheel graph S and is adjacent to it:(i)
Delete the upper-left and upper-right hub edges in eachW5 lying above the row R of LD(ii)
Delete the lower-left and lower-right hub edges in eachW5 lying below the row R of LD(iii)
Delete the upper-left and lower-left hub edges in eachW5 lying on the row R and left of wheel graph S(iv)
Delete the upper-right and lower-right hub edges in eachW5 lying on the line R and right of wheel graph S(v)
Delete the vertical edges in eachW5 lying on the row R(vi)
Furthermore, delete the upper-right edge ofS1, lower-left edge of S2, and upper-left edge of the S3
The resulting subgraph is denoted byQD (shown in Figure 7, for D=5,7,9,11), which is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD. This implies that QD is the biggest subgraph of G of maximal valency Δ=6 and diameter D.Figure 7
The biggest subgraphs ofG for D=3,5,7,9,11 and Δ=6.


### 4.4. Values forΔ=5

Theorem 7.
LetD be an even natural number, and let G be the infinite enhanced mesh network. Then,(11)NG5,D=6,forD=2,NG5,D≥22,forD=4,NG5,D=VLD,forD=2k,k∈ℕ−1,2.Proof.
ForD=2, the graph contains K1,5. This is the biggest subgraph of G of maximal valency 5, since in graph LD (shown in Figure 3(a)) of maximal valency Δ=8, the central node can be connected to at most 5 nodes. Hence, NG5,2=6.
ForD=4, the graph shown in Figure 8 is of maximal valency 5 and diameter 4, which is the subgraph of LD(shown in Figure 3(a)). Hence, NG5,2≥22.
ForD=2k,k∈3,4,…, Δ=5, we construct subgraph MD (shown in Figure 8) from LD as follows.
LetL and M be the horizontal and vertical lines passing through the central node n that divide LD into four regions (upper left, upper right, lower left, and lower right). Let H1, H2, and H3 be the wheel graphs W5 of LD lying in the upper-left, upper-right, and lower-left regions, respectively, at a distance zero from the central node n. Furthermore, suppose that x, y, and z be the hub vertices of H1, H2, and H3, respectively:(i)
Delete the upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges inLD except the edges lying on the horizontal line L(vi)
Delete all the vertical edges inLD except the edges lying on the vertical line M(vii)
Delete the three oblique edges ofH1, H2, and H3 that are adjacent to the central node n(viii)
Now reinstate the left vertical edge ofH1, right vertical edge of H2, and lower horizontal edge of H3
The resulting subgraph is denoted byMD (shown in Figure 7, for D=6,8,10), which is the spanning subgraph of LD; hence, VLD=VMD. Furthermore, the graph MD also has diameter D since the distance of all the nodes of MD from n is the same as in LD except the nodes x, y, and z. However, dx,n=2≤D/2,dy,n=2≤D/2 and dz,n=2≤D/2, for all D≥6. This implies that MD is the biggest subgraph of G of maximal valency Δ=5 and diameter D.Figure 8
M
D for D=4,6,8,10 and maximal valency Δ=5.Theorem 8.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(12)NG5,1=3,NG5,3≥11,NG5,5≥33,NG5,D=VLD,forD=2k+1,k∈ℕ−1,2.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 5. Hence, NG5,1=3.
ForD=3, the graph shown in Figure 9(a) is of maximal valency Δ=5 and diameter 3, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG5,3≥11.
ForD=5, the graph shown in Figure 9(a) is of maximal valency Δ=5 and diameter 5, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG5,3≥33.
ForD=2k+1,k∈ℕ−1,2, and Δ=5, we construct a subgraph QD (shown in Figure 9) from LD as follows.
LetL be the horizontal line passing through the edge bc of the central triangle T and R be the vertical column of wheel graphs W5 containing the central triangle T that divide the graph LD into four regions (upper left, upper right, lower left, and lower right), as shown in Figure 9(b). Let K be the wheel graph W5 that contains the central triangle T. Let K1 and K3 be the wheel graphs W5 lying in the lower-left and lower-right regions, respectively, at a distance zero from the central triangle T, both lying on the line L. Let K2 be the wheel graph W5 lying below the wheel graph K and is adjacent to it:(i)
Delete the upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges ofLD in the four regions except the edges that are lying on the horizontal line L(vi)
Delete all the vertical edges ofLD in the four regions except the edges that are lying on the vertical column R(vii)
Delete the left and right vertical edges of wheel graphK(viii)
Delete the upper-left and upper-right hub edges in the wheel graphK2(ix)
Delete the upper-right (upper-left) hub edge of the wheel graphK1K3(x)
Now, reinstate the left vertical edge ofK1 and right vertical edge of K3
The resulting subgraph is denoted byQD(shown in Figure 9, for D=7,9), which is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD except the nodes x, y, and z whose distance from central triangle T is ≤D−1/2. This implies that QD is the biggest subgraph of G of maximal valency Δ=5 and diameter D.Figure 9
The biggest subgraphs ofG for D=3,5,7,9 and Δ=5.


### 4.5. Values and Bounds forΔ=4

Now, we discuss the case whenΔ=4.For evenD, we prove the succeeding theorem.Theorem 9.
LetG be the infinite enhanced mesh and D be an even natural number. Then,(13)NG4,D=5,forD=2,NG4,D≥17,forD=4,NG4,D≥41,forD=6,NG4,D≥VLD−4,forD=2k,k∈ℕ−1,2,3.Proof.
The lower bound forNG4,2 is 5, since the graph contains K1,4. The biggest subgraph of G of maximal valency 8 is the graph LD (shown Figure 3(a)). When Δ=4, the central node n of LD can be connected to at most four vertices. Therefore, we have to remove at least four vertices, which are adjacent to n, otherwise D>2. This implies that the biggest subgraph of G of maximal valency 4 can contain at most 5 vertices. Hence, NG4,2=5.
ForD=4, the graph G contains the subgraph (shown in Figure 10(a)) that has maximal valency and diameter 4. Thus, NG4,D≥17.
ForD=6, the graph G contain the subgraph (shown in Figure 10(a)) that has maximal valency 4 and diameter 6. Thus, NG4,D≥41.
ForD=2k,k∈3,4,…, and Δ=4, we construct a subgraph MD (shown in Figure 10) from LD as follows.
LetL and M be the horizontal and vertical lines, respectively, passing through the central node n that divide LD into four regions (upper left, upper right, lower left, and lower right). Let H1, H2, H3, and H4 be the wheel graphs W5 of LD lying in the upper-left, upper-right, lower-left, and lower-right regions, respectively, at a distance 1 from the central node n and lying on the line L. Let P1 be the path of length D passing through the central node n and lies in upper-left and lower-right regions. Let P2 be the path of length D passing through the central node n and lies in upper-right and lower-left regions. Furthermore, suppose that the nodes u and v lie on the path P1 and w and x lie on the path P2 that are adjacent to the central node n:(i)
Delete the upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges inLD except the edges lying on the line L(vi)
Delete all the vertical edges inLD except the edges lying on the line M(vii)
Delete the four oblique edgesun, vn, wn, and xn that are adjacent to the central node n(viii)
Delete both the end vertices of pathsP1 and P2(ix)
Now, reinstate the upper-right hub edge ofH1, upper-left hub edge of H2, lower-right hub edge of H3, and lower-left hub edge of H4
The resulting subgraph is denoted byMD (shown in Figure 10 for D=8,10). Furthermore, the graph MD has also diameter D since the distance of all the nodes of MD from n is the same as in LD except the nodes u, v, w, and x whose distance from n is ≤D/2 for all D≥8. Since MD is obtained from LD by deleting only four nodes of LD, which implies that VMD=VLD−4.
Hence,NG4,D≥VLD−4.Figure 10
The subgraphsMD of G for D=4,6,8,10 and Δ=4.Theorem 10.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(14)NG4,1=3,NG4,3≥9,NG4,5≥27,NG4,7≥59,NG4,D=VLD,forD=2k+1,k∈ℕ−1,2,3.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 4. Hence, NG4,1=3.
ForD=3, the graph shown in Figure 11(a) is of maximal valency Δ=4 and diameter 4, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG4,3≥9.
ForD=5, the graph shown in Figure 11(a) is of maximal valency Δ=4 and diameter 5, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG4,5≥27.
ForD=7, the graph shown in Figure 11(b) is of maximal valency Δ=4 and diameter 7, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG4,7≥59.
ForD=2k+1,k∈ℕ−1,2,3, and Δ=4, we construct a subgraph QD (shown in Figure 11) from LD as follows
LetL be the horizontal line passing through the edge bc of the central triangle T and R be the vertical column of wheel graphs W5 containing the central triangle T that divide the graph LD into four regions (upper left, upper right, lower left, and lower right). Let K be the wheel graph W5 that contains the central triangle T. Let K1 and K3 be the wheel graphs W5 lying in the lower-left and lower-right regions, respectively, at a distance 1 from the central triangle T, both lying on the line L. Let K2 be the wheel graph W5 lying below the wheel graph K and is adjacent to it. Let K4K6 be the wheel graph W5 lying on left (right) of the wheel graph K and is adjacent to it. Let K5 be the wheel graph W5 lying above the wheel graph K and is adjacent to it:(i)
Delete upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges ofLD in the four regions except the edges that are lying on the line L(vi)
Delete all the vertical edges ofLD in the four regions except the edges that are lying in the column R(vii)
Delete the left and right vertical edges ofK(viii)
Delete the upper-left, upper-right, and lower-right hub edges in eachW5 lying in the column R and above K except K5(ix)
Delete the lower-left, lower-right, and upper-left hub edges in eachW5 lying in the column R and below K except K2(x)
Delete the upper-left, upper-right, and lower-right hub edges inK2(xi)
Delete the lower-left, lower-right, and upper-left hub edges inK5(xii)
Furthermore, delete the edgesyb, wb, tc, and uc(xiii)
Now, reinstate the lower horizontal edges inK1 and K3(xiv)
Now, reinstate the upper horizontal edges inK4 and K6
The resulting subgraph is denoted byQD (shown in Figure 11(b), for D=9), which is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD except the nodes s, t, u, v, w, x, y, and z whose distance from central triangle T is ≤D−1/2. This implies that QD is the biggest subgraph of G of maximal valency Δ=4 and diameter D.Figure 11
The biggest subgraphs ofG for D=3,5,7,9 and Δ=4.


### 4.6. Bounds forΔ=3

ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 3. Hence, NG3,1=3.The lower bound forNG3,2 is 4, since the graph contains K1,3. The biggest subgraph of G of maximal valency 8 is the graph LD (shown in Figure 3(a)). When Δ=3, the central node n of LD can be connected to at most three nodes. Therefore, we have to remove at least three nodes which are adjacent to n, otherwise D>2. This implies that the biggest subgraph of G of maximal valency 3 can contain at most 4 nodes. Hence, NG3,2=4.Theorem 11.
LetG be the infinite enhanced mesh network and D be an even natural number. Then,(15)NG3,D≥10,forD=4,22,forD=6,46,forD=8,VLD−8k+33,forD=2k+8,k∈ℕ.Proof.
ForD=4,6,8, the subgraphs of G shown in Figure 12 are of maximal valency Δ=3. It is also easy to check that the diameter of each graph is D. Hence, the theorem is true for D=4,6,8.
ForD=2k+8, LD is the biggest subgraph of G of maximal valency Δ=8 and diameter D. Let WD be the subgraph of LD of maximal valency Δ=3 and diameter D. The structure of the graph WD for D=10,12,14 is depicted in Figure 12. The central node of graph WD correspond to the central node of LD and is exhibited by •. The whole graph WD is constructed from LD by deleting those nodes which have distance greater than D/2 from the central node n. The structure of the deleted nodes in the construction of WD is shown in Figure 12. To calculate the deleted nodes of LD, we draw horizontal lines on deleted nodes and counting them in horizontal rows from top to bottom:
Delete vertices inLD=2+3+3+3+⋯tok+1terms+4+2k+8+2+5+4+3+3+3+⋯tok+1terms+2=8k+33.
Hence,WD=VLD−8k+33 for D=2k+8.
Furthermore,dx,n≤D/2 for every node x∈WD. Thus, WD has diameter at most D.
Hence, the theorem is satisfied forD=2k+8,k∈ℕ.Figure 12
The subgraphs ofG for D=4,6,8,10,12,14 and Δ=3.Theorem 12.
LetG be the infinite enhanced mesh network and D be an odd natural number. Then,(16)NG3,D≥6,forD=3,14,forD=5,29,forD=7,56,forD=9,VLD−8k+38,forD=2k+9.Proof.
ForD=3,5,7,9, the subgraphs of G shown in Figure 13 are of maximal valency Δ=3. It is also easy to check that each graph has a diameter D. Hence, the theorem is true for D=3,5,7,9.
ForD=2k+9, LD is the biggest subgraph of G of maximal valency Δ=8 and diameter D. Let WD be the subgraph of LD of maximal valency Δ=3 and diameter D. The structure of the graph WD for D=11,13,15 is exhibited in Figure 13. The central triangle of WD correspond to the central triangle T of LD and is depicted by •. The whole graph WD is constructed from LD by deleting those nodes which have distance greater than D−1/2 from the central triangle T. The structure of the deleted nodes in the construction of WD is shown in Figure 13. Now, calculate the deleted nodes of LD in horizontal rows from top to bottom.
Delete Vertices inLD=3+3+3+⋯tok+2terms+4+2k+9+2+4+5+5+3+3+3+⋯tokterms+2+1=8k+38.
Hence,WD=VLD−8k+38 for D=2k+9, k∈ℕ.
Furthermore,dx,T≤D−1/2 for every node x∈WD. Thus, WD has diameter at most D.
Hence, the theorem is satisfied forD=2k+9,k∈ℕ.
Using the result from Theorems11 and 12 and the fact that NGΔ−1,D≤NGΔ,D for any graph, we get the succeeding statement.Figure 13
The subgraphs ofG for D=3,5,7,9,11,13,15 and Δ=3.Corollary 2.
LetG be the infinite enhanced mesh network and let D≥10 is a natural number. Then, for k∈ℕ,(17)VLD−8k+33≤NG3,D≤VLDforD=2k+8,VLD−8k+38≤NG3,D≤VLDforD=2k+9.


## 4.1. Values forΔ=1,2

IfΔ=1, then the biggest connected subgraph of G is just an edge and hence NG1,D=K2.Now, we discuss the case whenΔ=2.Theorem 2.
LetG be the enhanced mesh network, and let D be a natural number. Then,(6)NG2,D=2D,whenD≥2.Proof.
ForD=2k,k∈ℕ. Let L and M be the horizontal and vertical lines, respectively, that are passing through the central node n of LD and divide the graph LD into four regions (upper left, upper right, lower left, and lower right), as shown in Figure 3. Consider a border cycle C of the lower-left region containing the central node (see the blue cycle in Figure 3(a)). Cycle C has 2D nodes.
ForD=2k+1,k∈ℕ. Let Q be the horizontal line passing through the edge bc and R be the vertical line passing through the node c of the triangle T in the graph LD that divide the graph LD into four regions (upper left, upper right, lower left, and lower right), as shown in Figure 3. Consider a border cycle C of the lower-left region containing the edge bc(see the blue cycle in Figure 3(b)). The cycle C has 2D nodes.Figure 3
The biggest subgraphLD for D=2,4,5,6,7 and Δ=2.
(a)
(b)


## 4.2. Values forΔ=7

Theorem 3.
LetD be an even natural number, and let G be an infinite enhanced mesh network. Then,(7)NG7,D=8,forD=2,NG7,D=VLD,forD=2k,k∈ℕ−1.Proof.
ForD=2, the graph contains K1,7, which is the biggest subgraph of G of valency 7, since in the graph LD (shown in Figure 3(a)) of maximal valency Δ=8, the central node can be attached to at most 7 nodes. Hence, NG7,2=8.
ForD=2k,k∈2,3,4,…, and Δ=7, we construct a subgraph MD (shown in Figure 4) from LD as follows.
LetL be the central horizontal line passing through the central node n, M be the upper neighboring row, and N be the lower neighboring row. Let H be the wheel graph W5 of LD lying on and above the central line at a distance zero on the right side of the central node n. Furthermore, suppose that x is the hub node of H:(i)
Delete the upper-left and upper-right hub edges in eachW5 lying on and above the line L of LD(ii)
Delete the lower-left and lower-right hub edges in eachW5 lying on and below the line L of LD(iii)
Delete the lower-left hub edge (lower-right hub edge) on left of the central noden(on the right of the central node n) in each W5 lying between the horizontal lines L and M of LD, except the wheel graph H whose lower-left hub edge is deleted(iv)
Delete the upper-left hub edge (upper-right hub edge) on left of the central noden(on right of the central node n) in each W5 lying between the lines L and N of the graph LD
The resulting subgraph is denoted byMD (shown in Figure 4, for D=4,6,8,10) which is the spanning subgraph of LD; hence, VLD=VMD. Furthermore, graph MD also has diameter D since the distance of all the nodes of MD from n is the same as in LD except the node x. However, dx,n=2≤D/2, for all D≥4. This implies that MD is the biggest subgraph of G of maximal valency Δ=7 and diameter D.Figure 4
M
D for D=4,6,8,10 and maximal valency Δ=7.Theorem 4.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(8)NG7,1=3,NG7,D=VLD,forD=2k+1,k∈ℕ.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 7. Hence, NG7,1=3.
ForD=2k+1,k∈ℕ, andΔ=7, we construct a subgraph QD (shown in Figure 5) from LD as follows.
LetL be the horizontal line passing through edge bc of the central triangle T of graph LD and M be the upper neighboring horizontal row. Let K be the wheel subgraph of LD containing the central triangle T:(i)
Delete the upper-left and upper-right hub edges in eachW5 lying on and above the line M of LD(ii)
Delete the lower-left and lower-right hub edges in eachW5 lying on and below the line L of LD(iii)
Delete the upper-left, lower-left hub edges in eachW5 lying on the left of wheel graph K.(iv)
Delete the upper-right and lower-right hub edges in eachW5 lying on the right of wheel graph K(v)
Furthermore, delete the left and right vertical edges in the wheel graphK
The resulting subgraph is denoted byQD (shown in Figure 5 for D=5,7,9,11) is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD. This implies that QD is the biggest subgraph of G of maximal valency Δ=7 and diameter D.Figure 5
The biggest subgraphs ofG for D=3,5,7,9,11 and Δ=7.


## 4.3. Values forΔ=6

Theorem 5.
LetD be an even natural number, and let G be the infinite enhanced mesh network. Then,(9)NG6,D=7,forD=2,NG6,D=VLD,forD=2k,k∈ℕ−1.Proof.
ForD=2, the graph contains K1,6. This is a biggest subgraph of G of maximal valency 6 since in the graph LD (shown in Figure 3(a)) of maximal valency Δ=8, and the central node can be connected to at most 6 nodes. Hence, NG6,2=7.
ForD=2k,k∈2,3,4,…, Δ=6, we construct a subgraph MD (shown in Figure 6) from LD as follows.
LetL and M be the horizontal and vertical lines passing through the central node n that divide LD into four regions (upper left, upper right, lower left, and lower right). Let H and K be the wheel graphs W5 of LD lying in the upper-right and lower-left regions at a distance 0 from the central node n. Furthermore, suppose that x and y be the hub vertices of H and K, respectively:(i)
Delete the upper-left, upper-right, and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-left, upper-right, and lower-right hub edges in eachW5 lying in the upper-right region of LD except the wheel graph H(iii)
Delete the lower-left, lower-right, and upper-left hub edges in eachW5 lying in the lower-left region of LD except the wheel graph K(iv)
Delete the lower-left, lower-right, and upper-right hub edges in eachW5 lying in the lower-right region of LD(v)
Furthermore, delete the upper-left, upper-right, lower-left hub edges, and right vertical edge inH; also, delete the lower-left, lower-right, upper-right hub edges, and left vertical edge in K
The resulting subgraph is denoted byMD (shown in Figure 6, for D=4,6,8,10), which is the spanning subgraph of LD; hence, VLD=VMD. Furthermore, the graph MD also has diameter D since the distance of all the nodes of MD from n is the same as in LD except the nodes x and y. However, dx,n=2≤D/2,dy,n=2≤D/2, for all D≥4. This implies that MD is the biggest subgraph of G of maximal valency Δ=6 and diameter D.Figure 6
M
D for D=4,6,8,10 and maximal valency Δ=6.Theorem 6.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(10)NG6,1=3,NG6,3=13,NG6,D=VLD,forD=2k+1,k∈ℕ.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 6. Hence, NG6,1=3.
ForD=3, the graph LD of maximal valency 8 is a closed ball of radius 3 (shown Figure 3(b)). For maximal valency Δ=6, the biggest subgraph cannot contain all the nodes of the graph LD, otherwise D=4. Thus, the graph shown in Figure 7(a) is the biggest subgraph of maximal valency Δ=6. Hence, NG6,3=13.
ForD=2k+1,k∈ℕ, and Δ=6, we construct a subgraph QD(shown in Figure 7) from LD as follows.
LetS be the wheel graph W5 that contains the central triangle T. Let R be the horizontal row of the wheel graphs W5 containing the wheel graph S. Let S1S2 be the wheel graphs lying on left (right) of S and is adjacent to it. Also, let S3 be the wheel graph W5 below the wheel graph S and is adjacent to it:(i)
Delete the upper-left and upper-right hub edges in eachW5 lying above the row R of LD(ii)
Delete the lower-left and lower-right hub edges in eachW5 lying below the row R of LD(iii)
Delete the upper-left and lower-left hub edges in eachW5 lying on the row R and left of wheel graph S(iv)
Delete the upper-right and lower-right hub edges in eachW5 lying on the line R and right of wheel graph S(v)
Delete the vertical edges in eachW5 lying on the row R(vi)
Furthermore, delete the upper-right edge ofS1, lower-left edge of S2, and upper-left edge of the S3
The resulting subgraph is denoted byQD (shown in Figure 7, for D=5,7,9,11), which is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD. This implies that QD is the biggest subgraph of G of maximal valency Δ=6 and diameter D.Figure 7
The biggest subgraphs ofG for D=3,5,7,9,11 and Δ=6.


## 4.4. Values forΔ=5

Theorem 7.
LetD be an even natural number, and let G be the infinite enhanced mesh network. Then,(11)NG5,D=6,forD=2,NG5,D≥22,forD=4,NG5,D=VLD,forD=2k,k∈ℕ−1,2.Proof.
ForD=2, the graph contains K1,5. This is the biggest subgraph of G of maximal valency 5, since in graph LD (shown in Figure 3(a)) of maximal valency Δ=8, the central node can be connected to at most 5 nodes. Hence, NG5,2=6.
ForD=4, the graph shown in Figure 8 is of maximal valency 5 and diameter 4, which is the subgraph of LD(shown in Figure 3(a)). Hence, NG5,2≥22.
ForD=2k,k∈3,4,…, Δ=5, we construct subgraph MD (shown in Figure 8) from LD as follows.
LetL and M be the horizontal and vertical lines passing through the central node n that divide LD into four regions (upper left, upper right, lower left, and lower right). Let H1, H2, and H3 be the wheel graphs W5 of LD lying in the upper-left, upper-right, and lower-left regions, respectively, at a distance zero from the central node n. Furthermore, suppose that x, y, and z be the hub vertices of H1, H2, and H3, respectively:(i)
Delete the upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges inLD except the edges lying on the horizontal line L(vi)
Delete all the vertical edges inLD except the edges lying on the vertical line M(vii)
Delete the three oblique edges ofH1, H2, and H3 that are adjacent to the central node n(viii)
Now reinstate the left vertical edge ofH1, right vertical edge of H2, and lower horizontal edge of H3
The resulting subgraph is denoted byMD (shown in Figure 7, for D=6,8,10), which is the spanning subgraph of LD; hence, VLD=VMD. Furthermore, the graph MD also has diameter D since the distance of all the nodes of MD from n is the same as in LD except the nodes x, y, and z. However, dx,n=2≤D/2,dy,n=2≤D/2 and dz,n=2≤D/2, for all D≥6. This implies that MD is the biggest subgraph of G of maximal valency Δ=5 and diameter D.Figure 8
M
D for D=4,6,8,10 and maximal valency Δ=5.Theorem 8.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(12)NG5,1=3,NG5,3≥11,NG5,5≥33,NG5,D=VLD,forD=2k+1,k∈ℕ−1,2.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 5. Hence, NG5,1=3.
ForD=3, the graph shown in Figure 9(a) is of maximal valency Δ=5 and diameter 3, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG5,3≥11.
ForD=5, the graph shown in Figure 9(a) is of maximal valency Δ=5 and diameter 5, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG5,3≥33.
ForD=2k+1,k∈ℕ−1,2, and Δ=5, we construct a subgraph QD (shown in Figure 9) from LD as follows.
LetL be the horizontal line passing through the edge bc of the central triangle T and R be the vertical column of wheel graphs W5 containing the central triangle T that divide the graph LD into four regions (upper left, upper right, lower left, and lower right), as shown in Figure 9(b). Let K be the wheel graph W5 that contains the central triangle T. Let K1 and K3 be the wheel graphs W5 lying in the lower-left and lower-right regions, respectively, at a distance zero from the central triangle T, both lying on the line L. Let K2 be the wheel graph W5 lying below the wheel graph K and is adjacent to it:(i)
Delete the upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges ofLD in the four regions except the edges that are lying on the horizontal line L(vi)
Delete all the vertical edges ofLD in the four regions except the edges that are lying on the vertical column R(vii)
Delete the left and right vertical edges of wheel graphK(viii)
Delete the upper-left and upper-right hub edges in the wheel graphK2(ix)
Delete the upper-right (upper-left) hub edge of the wheel graphK1K3(x)
Now, reinstate the left vertical edge ofK1 and right vertical edge of K3
The resulting subgraph is denoted byQD(shown in Figure 9, for D=7,9), which is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD except the nodes x, y, and z whose distance from central triangle T is ≤D−1/2. This implies that QD is the biggest subgraph of G of maximal valency Δ=5 and diameter D.Figure 9
The biggest subgraphs ofG for D=3,5,7,9 and Δ=5.


## 4.5. Values and Bounds forΔ=4

Now, we discuss the case whenΔ=4.For evenD, we prove the succeeding theorem.Theorem 9.
LetG be the infinite enhanced mesh and D be an even natural number. Then,(13)NG4,D=5,forD=2,NG4,D≥17,forD=4,NG4,D≥41,forD=6,NG4,D≥VLD−4,forD=2k,k∈ℕ−1,2,3.Proof.
The lower bound forNG4,2 is 5, since the graph contains K1,4. The biggest subgraph of G of maximal valency 8 is the graph LD (shown Figure 3(a)). When Δ=4, the central node n of LD can be connected to at most four vertices. Therefore, we have to remove at least four vertices, which are adjacent to n, otherwise D>2. This implies that the biggest subgraph of G of maximal valency 4 can contain at most 5 vertices. Hence, NG4,2=5.
ForD=4, the graph G contains the subgraph (shown in Figure 10(a)) that has maximal valency and diameter 4. Thus, NG4,D≥17.
ForD=6, the graph G contain the subgraph (shown in Figure 10(a)) that has maximal valency 4 and diameter 6. Thus, NG4,D≥41.
ForD=2k,k∈3,4,…, and Δ=4, we construct a subgraph MD (shown in Figure 10) from LD as follows.
LetL and M be the horizontal and vertical lines, respectively, passing through the central node n that divide LD into four regions (upper left, upper right, lower left, and lower right). Let H1, H2, H3, and H4 be the wheel graphs W5 of LD lying in the upper-left, upper-right, lower-left, and lower-right regions, respectively, at a distance 1 from the central node n and lying on the line L. Let P1 be the path of length D passing through the central node n and lies in upper-left and lower-right regions. Let P2 be the path of length D passing through the central node n and lies in upper-right and lower-left regions. Furthermore, suppose that the nodes u and v lie on the path P1 and w and x lie on the path P2 that are adjacent to the central node n:(i)
Delete the upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges inLD except the edges lying on the line L(vi)
Delete all the vertical edges inLD except the edges lying on the line M(vii)
Delete the four oblique edgesun, vn, wn, and xn that are adjacent to the central node n(viii)
Delete both the end vertices of pathsP1 and P2(ix)
Now, reinstate the upper-right hub edge ofH1, upper-left hub edge of H2, lower-right hub edge of H3, and lower-left hub edge of H4
The resulting subgraph is denoted byMD (shown in Figure 10 for D=8,10). Furthermore, the graph MD has also diameter D since the distance of all the nodes of MD from n is the same as in LD except the nodes u, v, w, and x whose distance from n is ≤D/2 for all D≥8. Since MD is obtained from LD by deleting only four nodes of LD, which implies that VMD=VLD−4.
Hence,NG4,D≥VLD−4.Figure 10
The subgraphsMD of G for D=4,6,8,10 and Δ=4.Theorem 10.
LetD be an odd natural number, and let G be the infinite enhanced mesh network. Then,(14)NG4,1=3,NG4,3≥9,NG4,5≥27,NG4,7≥59,NG4,D=VLD,forD=2k+1,k∈ℕ−1,2,3.Proof.
ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 4. Hence, NG4,1=3.
ForD=3, the graph shown in Figure 11(a) is of maximal valency Δ=4 and diameter 4, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG4,3≥9.
ForD=5, the graph shown in Figure 11(a) is of maximal valency Δ=4 and diameter 5, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG4,5≥27.
ForD=7, the graph shown in Figure 11(b) is of maximal valency Δ=4 and diameter 7, which is a subgraph of LD (shown in Figure 3(b)). Hence, NG4,7≥59.
ForD=2k+1,k∈ℕ−1,2,3, and Δ=4, we construct a subgraph QD (shown in Figure 11) from LD as follows
LetL be the horizontal line passing through the edge bc of the central triangle T and R be the vertical column of wheel graphs W5 containing the central triangle T that divide the graph LD into four regions (upper left, upper right, lower left, and lower right). Let K be the wheel graph W5 that contains the central triangle T. Let K1 and K3 be the wheel graphs W5 lying in the lower-left and lower-right regions, respectively, at a distance 1 from the central triangle T, both lying on the line L. Let K2 be the wheel graph W5 lying below the wheel graph K and is adjacent to it. Let K4K6 be the wheel graph W5 lying on left (right) of the wheel graph K and is adjacent to it. Let K5 be the wheel graph W5 lying above the wheel graph K and is adjacent to it:(i)
Delete upper-right and lower-left hub edges in eachW5 lying in the upper-left region of LD(ii)
Delete the upper-right and lower-left hub edges in eachW5 lying in the lower-right region of LD(iii)
Delete the upper-left and lower-right hub edges in eachW5 lying in the upper-right region of LD(iv)
Delete the upper-left and lower-right hub edges in eachW5 lying in the lower-left region of LD(v)
Delete all the horizontal edges ofLD in the four regions except the edges that are lying on the line L(vi)
Delete all the vertical edges ofLD in the four regions except the edges that are lying in the column R(vii)
Delete the left and right vertical edges ofK(viii)
Delete the upper-left, upper-right, and lower-right hub edges in eachW5 lying in the column R and above K except K5(ix)
Delete the lower-left, lower-right, and upper-left hub edges in eachW5 lying in the column R and below K except K2(x)
Delete the upper-left, upper-right, and lower-right hub edges inK2(xi)
Delete the lower-left, lower-right, and upper-left hub edges inK5(xii)
Furthermore, delete the edgesyb, wb, tc, and uc(xiii)
Now, reinstate the lower horizontal edges inK1 and K3(xiv)
Now, reinstate the upper horizontal edges inK4 and K6
The resulting subgraph is denoted byQD (shown in Figure 11(b), for D=9), which is the spanning subgraph of LD; hence, VLD=VQD. Furthermore, the graph QD also has diameter D since the distance of all the nodes of QD from the central triangle is the same as in LD except the nodes s, t, u, v, w, x, y, and z whose distance from central triangle T is ≤D−1/2. This implies that QD is the biggest subgraph of G of maximal valency Δ=4 and diameter D.Figure 11
The biggest subgraphs ofG for D=3,5,7,9 and Δ=4.


## 4.6. Bounds forΔ=3

ForD=1, the graph contains K3 and this is a biggest induced subgraph of G of maximal valency 3. Hence, NG3,1=3.The lower bound forNG3,2 is 4, since the graph contains K1,3. The biggest subgraph of G of maximal valency 8 is the graph LD (shown in Figure 3(a)). When Δ=3, the central node n of LD can be connected to at most three nodes. Therefore, we have to remove at least three nodes which are adjacent to n, otherwise D>2. This implies that the biggest subgraph of G of maximal valency 3 can contain at most 4 nodes. Hence, NG3,2=4.Theorem 11.
LetG be the infinite enhanced mesh network and D be an even natural number. Then,(15)NG3,D≥10,forD=4,22,forD=6,46,forD=8,VLD−8k+33,forD=2k+8,k∈ℕ.Proof.
ForD=4,6,8, the subgraphs of G shown in Figure 12 are of maximal valency Δ=3. It is also easy to check that the diameter of each graph is D. Hence, the theorem is true for D=4,6,8.
ForD=2k+8, LD is the biggest subgraph of G of maximal valency Δ=8 and diameter D. Let WD be the subgraph of LD of maximal valency Δ=3 and diameter D. The structure of the graph WD for D=10,12,14 is depicted in Figure 12. The central node of graph WD correspond to the central node of LD and is exhibited by •. The whole graph WD is constructed from LD by deleting those nodes which have distance greater than D/2 from the central node n. The structure of the deleted nodes in the construction of WD is shown in Figure 12. To calculate the deleted nodes of LD, we draw horizontal lines on deleted nodes and counting them in horizontal rows from top to bottom:
Delete vertices inLD=2+3+3+3+⋯tok+1terms+4+2k+8+2+5+4+3+3+3+⋯tok+1terms+2=8k+33.
Hence,WD=VLD−8k+33 for D=2k+8.
Furthermore,dx,n≤D/2 for every node x∈WD. Thus, WD has diameter at most D.
Hence, the theorem is satisfied forD=2k+8,k∈ℕ.Figure 12
The subgraphs ofG for D=4,6,8,10,12,14 and Δ=3.Theorem 12.
LetG be the infinite enhanced mesh network and D be an odd natural number. Then,(16)NG3,D≥6,forD=3,14,forD=5,29,forD=7,56,forD=9,VLD−8k+38,forD=2k+9.Proof.
ForD=3,5,7,9, the subgraphs of G shown in Figure 13 are of maximal valency Δ=3. It is also easy to check that each graph has a diameter D. Hence, the theorem is true for D=3,5,7,9.
ForD=2k+9, LD is the biggest subgraph of G of maximal valency Δ=8 and diameter D. Let WD be the subgraph of LD of maximal valency Δ=3 and diameter D. The structure of the graph WD for D=11,13,15 is exhibited in Figure 13. The central triangle of WD correspond to the central triangle T of LD and is depicted by •. The whole graph WD is constructed from LD by deleting those nodes which have distance greater than D−1/2 from the central triangle T. The structure of the deleted nodes in the construction of WD is shown in Figure 13. Now, calculate the deleted nodes of LD in horizontal rows from top to bottom.
Delete Vertices inLD=3+3+3+⋯tok+2terms+4+2k+9+2+4+5+5+3+3+3+⋯tokterms+2+1=8k+38.
Hence,WD=VLD−8k+38 for D=2k+9, k∈ℕ.
Furthermore,dx,T≤D−1/2 for every node x∈WD. Thus, WD has diameter at most D.
Hence, the theorem is satisfied forD=2k+9,k∈ℕ.
Using the result from Theorems11 and 12 and the fact that NGΔ−1,D≤NGΔ,D for any graph, we get the succeeding statement.Figure 13
The subgraphs ofG for D=3,5,7,9,11,13,15 and Δ=3.Corollary 2.
LetG be the infinite enhanced mesh network and let D≥10 is a natural number. Then, for k∈ℕ,(17)VLD−8k+33≤NG3,D≤VLDforD=2k+8,VLD−8k+38≤NG3,D≤VLDforD=2k+9.


## 5. Conclusion

In the Degree Diameter Problem, the largest graphs in term of vertices are computed with given degree and diameter. In this work, we have considered the restricted version of Degree Diameter Problem which states that given connected undirected host graphG, an upper bound D for the maximum degree, and an upper bound Δ for the diameter find the largest connected subgraph of maximum degree ≤Δ and diameter ≤D. This problem becomes of particular interest when we consider the host graph as the network.The topology of a network (such as a telecommunications, multiprocessor, or local area network, to name just a few) is usually modeled by a graph in which vertices represent ‘nodes’ (stations or processors) while undirected or directed edges stand for ‘links’ or other types of connections. There are many important features in the designing of such networks. One of the important aspects is to put limitation on vertex degree and its diameter. These two parameters in networks are interpreted as follows. By the degree of a node, it is meant to have the number of connections attached to that node; on the contrary, the diameter shows the largest number of links that must be required to transmit a message between any two nodes. The natural question that arises in this case is “what is then the largest number of nodes in a network with a limited degree and diameter?” If we design the network so that there is no directed edge, then this leads to the Degree/Diameter Problem.Planar graphs are popular for network design because they have a convenient physical layout. Of all planar network topologies, the (square) mesh is the most popular and this has been studied in [1, 3–5, 7]. In this work, we have extended this study by considering the host graph G as the graph obtained from the enhanced mesh network.In future, it will be interesting to find more such mesh networks and study the optimal subgraphs.Furthermore, we can extend this study to directed networks.



---

*Source: 9869201-2020-05-01.xml*