# Degree Diameter Problem on Oxide Network

^{*}

**Corresponding Author:**Akhtar MS, Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan, Tel: +92 61 9210097, Email: [email protected]

*
Received Date: Jul 20, 2017 /
Accepted Date: Jan 03, 2018 /
Published Date: Jan 10, 2018 *

### Abstract

The degree diameter problem is the problem of finding the largest graph (in terms of number of vertices) subject to the constraints on the degree and the diameter of the graph. Beyond the degree constraint there is no restriction on the number of edges (apart from keeping the graph simple) so the resulting graph may be thought of as being embedded in the complete graph. In a generalization of this problem, the graph is considered to be embedded in some connected host graph. This article considers embedding the graph in the oxide network and provides some exact values and some upper and lower bounds for the optimal graphs.

**Keywords:**
Oxide network; Degree; Diameter; Silicon vertex; Oxygen vertex; Closed ball; Tetrahedron; Triangle

#### Introduction

All graphs considered in this paper are simple, finite and undirected. The degree of a vertex in the graph G is the number of edges incident with that vertex in G. The maximum and minimum degree of the graph G is denoted by Δ(G) and δ(G), respectively. The distance between two vertices x and y of G is the length of the shortest path between them. The distance between a vertex x and the set A is defined as d(x,A)=min_{a∈A}d(x,a). The diameter of the graph G is denoted by D and is defined as the maximum pairwise distance between the vertices of the graph G. For a given graph G and positive integers Δ and D, N_{G}(Δ,D) denote the order of a largest subgraph of G with given maximum degree Δ and given diameter D. For definitions and notations not defined here we refer to the text [1-4]. The degree/ diameter problem (DDP) is a quest to find the largest graphs, in terms of the number of vertices, given constraints on the maximum degree of the graph and its diameter [5-10]. For a thorough survey of the state of the problem [11,12]. Because the maximum degree is the only restriction on the distribution of edges, there is considerable freedom in placing edges so as to avoid violating the diameter constraint. The degree diameter problem of honeycomb and triangular networks have been studied [5,6]. The largest sub graph N_{G}(Δ,D) have been determined with multidimensional rectangular Mesh and the multidimensional hexagonal grid as host graphs [7,10].

Silicates are obtained by fusing metal oxides or metal carbonates with sand. Essentially all the silicates contain Sio_{4} tetrahedra. In chemistry, the corner vertices of sio_{4} tetrahedron represent oxygen ions and the center vertex represents the silicon ion [2]. In graph theory, the tetrahedra unit sio_{4} is the complete graph K_{4}. We call the corner vertices as oxygen nodes and the center vertex as silicon node.

The graph of silicate network can be constructed in different ways [3]. The silicate network SL(1) is a cyclic silicate with six Sio_{4} tetrahedra units. The silicate network SL(2) is obtained by adding six units of SL(1) such that each outer SL(1) shares two consecutive tetrahedra of inner SL(1). Inductively, silicate network SL(n) of dimension n is obtained from SL(n-1) by adding a layer of SL(1) around the boundary of SL(n-1). The number of nodes in SL(n) is 15n^{2+}3n and the number of edges of SL(n) is 36n^{2}. In **Figure 1a**, a silicate network of dimension two is shown [2].

#### The Graph of Oxide Network

When all the silicon nodes are deleted from a silicate network, we obtain a new network which we shall call as an oxide network. An n-dimensional oxide network is denoted by OX(n) having number of vertices 9n^{2}+3n and number of edges 18n^{2} [4]. An oxide network of dimension 2 is shown in **Figure 1b** [4]. The distance of a vertex x∈V (G) from a triangle T is min_{y∈V(T)}d_{G}(x,y) and will be denoted by d_{G}(x,T), where the vertex y is the closest vertex of T from x. The properties of oxide networks have been studied in various aspect [2-4]. In this paper, we have studied the degree diameter problem of oxide networks.

In the following sections, we consider the cases when Δ=4 and Δ=1,2,3 separately.

#### Values for Δ=4

Let X denote the infinite oxide network in the Euclidean plane and we consider X as a host graph. Note that Δ(X)=4.

**Proposition 1.1**

For even D ≥ 4, Let the induced sub graph of X denoted by O_{D} is a closed ball of radius with center as a common vertex m of two triangles with vertex set then

(1)

where k∈N.

**Proof**

For even D ≥ 4, O_{D} is the closed ball of radius with center as a common vertex of two triangles and Δ=4. Now we draw horizontal lines on the vertices of O_{D} and count the vertices on each horizontal line one by one then adding them for top to bottom we have.

For D=4k, k∈ℕ, then

|V (O_{D})|=2k+(k+1)+...+(4k−3)+(2k−1)+(4k−1)+2k+(4k +1)+2k+(4k−1)+(2k −1)+...+(2k+3)+(k+1)+2k = 9k^{2}+5k

For D=4k+2, k∈ℕ, then

|V (O_{D})|=(k+1)+(2k+3)+...+(4k−1)+2k+(4k+1)+(2k+1) + (4k+3)+(2k+1)+(4k+1)+2k+(4k−1)+...+(2k+3)+(k+1) = 9k^{2}+13k+5

In the **Figures 2a and 2b** the graphs O_{D} for D=4 and D=6 are depicted where the central vertex n of O_{D} is depicted by ⊗.

**Proposition 1.2**

For odd D>4, Let the induced sub graph of X denoted by

O_{D} is a closed ball of radius with center as a triangle with vertex set , where n is the vertex of the central triangle which is closest to x then

(2)

where k∈ℕ

**Proof**

For odd D>4, O_{D} is the closed ball of radius with center as a triangle and Δ=4. Now we draw horizontal lines on the vertices of O_{D} and count the vertices on each horizontal line one by one then adding them for top to bottom we have.

For D=4k+1, k∈ℕ, then

|V (O_{D})|=(2k+2)+(k+1)+...+(4k−2)+(2k−1)+4k+2k+(4k + 2)+(2k+1)+4k+2k+(4k−2)+...+(k+1)+(2k+2) = 9k^{2+}9k+3

For D=4k+3, k∈ℕ, then

|V (O_{D})|=(k+2)+(2k+4)+....+4k+(2k+1)+(4k+2)+(2k+2) + (4k+4)+(2k+1)+(4k+2)+2k+4k+....+(k+1)+(2k+2) = 9k^{2+}18k+9

In the **Figures 3a and 3b** the graphs O_{D} for D=5 and D=7 are depicted. Where the vertices of central triangle of O_{D} are denoted by a,b,c and is depicted by ⊗.

Hence we proved the following statement.

**Theorem 1.3**

Let X be the infinite oxide network. Then for the largest connected sub graph of X of maximum degree Δ=4 and diameter D in terms of vertices we have the following two cases.

**Case (i)**

For D=4k,k∈ℕ, the largest connected subgraph of X with Δ=4 denoted by H_{D} is obtained by connecting the two oxygen vertices of the closed ball O_{D} with only one vertex of X. Such subgraph H_{D} for D=4 is shown in **Figure 4**.

N_{X}(4,D)=|V (H_{D})|=|V (O_{D})|+1 for D=4k,k∈ℕ

**Case (ii)**

For D=4k+r,k∈ℕ,r∈{1,2,3}, the largest subgraph of X with Δ=4 is O_{D} itself.

N_{X}(4,D)=|V (O_{D})| for D=4k+r,k∈ℕ,r∈{1,2,3}.

The following statement is an immediate consequence of the previous theorem.

**Corollary 1.4**

Let X be the infinite oxide network. Let Δ,D be positive integers, Δ ≤ 4 and D=4k+r,k∈ℕ,r∈{0,1,2,3}.Then we have.

**Case (i)**

N_{X}(Δ,D) ≤ |V (H_{D})| for D=4k,k∈ℕ.

**Case (ii)**

N_{X}(Δ,D) ≤ |V (O_{D})| for D=4k+r,k∈ℕ,r∈{1,2,3}.

#### Values for Δ ≤ 3

**Values for Δ=1,2**

Since for Δ ≥ Δ(X) we have

N_{X}(Δ,D)=|V (H_{D})|=|V (O_{D})|+1 for D=4k,k∈ℕ.And

N_{X}(Δ,D)=|V (O_{D})| for D=4k+r,k∈ℕ, r∈{1,2,3}.

Now we consider the cases when maximum degree Δ ≤ 3.

Since for Δ=1 and diameter D=4k+r, k∈ℕ, r∈{0,1,2,3}, the largest sub graph of X is a complete graph K_{2}.

Hence N_{X}(1,D)=2.

Now we discuss the case when Δ=2.

**Theorem 2.1**

Let X be the infinite oxide network, then for D ≥ 4 we have N_{X}(2,D)=2D+1.

**Proof**

**Case (i)**

For D=4k,k∈ℕ, clearly the graph H_{D} contains a cycle. Thus for D=4k,k∈ℕ, a largest subgraph of X having maximum degree 2 is a cycle of length 2D+1.

In the **Figure 5a**, for D=4 and Δ=2, such a cycle n→a→b→c→d→e→f→g→h→n of length 2D+1 in H_{D} is shown. which implies that For D=4k,k∈ℕ, such a sub graph of H_{D} exist.

**Case (ii)**

For D=4k,k∈ℕ,r∈{1,2,3}, Clearly the graph O_{D} contains a cycle. Thus for D=4k+r,k∈ℕ,r∈{1,2,3}, a largest subgraph of X having maximum degree 2 is a cycle of length 2D+1.

In the **Figure 5b**, such a cycle x→i→j→k→l→m→o→p→q→r→s→x for D=5 in O_{D} is shown. In the **Figure 5c**, such a cycle n→t→u→v→w→x→y→z→a→b→c→d→e→n for D=6 in O_{D} is shown. In the **Figure 5d**, such a cycle y→f→g→h→i→j→k→l→m→n→o→p→q→r→s→y for D=7 in O_{D} is shown, which implies that For D=4k+r,k∈ℕ,r∈{1,2,3}, such a subgraph of O_{D} exist.

Which completes the proof

#### Bounds for Δ=3

Now we find the bounds for Δ=3.

For even D ≥ 4, we have the following theorem.

**Theorem 2.2**

Let X be the infinite oxide network and D ≥ 4 be an even positive integer.

**Proof**

**Case (i)**

Clearly the largest degree of the graphs W_{D} (which are sub graphs of H_{D}, shown in **Figures 6a and 6b** is at most 3. Where the isolated vertices shown in it do not belongs to the vertex set of W_{D}. One can also check that the diameter of the graphs W_{D} is D. Hence the theorem holds for D=4,8.

Now we consider the graphs W_{D} (which are sub graphs of H_{D} for D=4k+8,k∈ℕ). Such graphs W_{D} for D=12,16,20 depicted in **Figures 6c, 7 and 8**, clearly having degree at most 3. Where the isolated vertices shown in the graphs do not belongs to the vertex set of W_{D}. Also one can easily check the diameter of W_{D} is D.

Since |V(H_{D})|=|V (W_{D})|+ the number of isolated vertices, for D=4k+8,k∈ℕ.

The number of isolated vertices form a sequence (2k+6) in the graphs W_{D} for D=4k+8, k∈ℕ. Hence the theorem holds for D=4k+8, k∈ℕ.

**Case (ii)**

Clearly the maximum degree of the graph W_{D} (which is a sub graph of O_{D}, shown in **Figure 9a** is at most 3. Where the isolated vertices shown in it do not belong to the vertex set of W_{D}. One can also check that the diameter of the graphs W_{D} is D. Hence the theorem holds for D=6.

Now we consider the graphs W_{D} (which are sub graphs of O_{D} for D=4k+6,k∈ℕ) clearly having degree at most 3. Such graphs W_{D} for D=10,14,18 are depicted in **Figures 9b, 9c and 10**. Where the isolated vertices shown in the graphs do not belong to the vertex set of W_{D}. Note that the central vertex n of W_{D} corresponds to the central vertex of O_{D} and is depicted by ⊗. Now we prove that the diameter of W_{D} is D. For this we have to prove that for every vertex x of W_{D}. Also one can easily check that all the vertices of W_{D} are at distance at most from the central vertex n. Hence the diameter of W_{D} is at most D. Since |V (O_{D})|= |V (W_{D})|+ the number of isolated vertices, for D=4k +6,k∈ℕ.

The number of isolated vertices form a sequence (k+5) in the graphs W_{D} for D=4k+6,k∈ℕ. Hence the theorem holds for D=4k+6,

Which completes the proof.

For odd D>4, we prove the following theorem.

**Theorem 2.3**

Let X be the infinite oxide network and D>4 be an odd positive integer. Then

(5)

and

(6)

**Proof:**

**Case (i)**

Now we consider the graphs W_{D} (which are sub graphs of O_{D} for D=4k+1,k∈ℕ). Such graphs W_{D} for D=5,9,13,17 are depicted in **Figures 11a, 11b, 11c and 1**2, clearly having degree at most 3. Where the isolated vertices shown in the graphs do not belongs to the vertex set of W_{D}. Note that the central triangle of W_{D} corresponds to the central triangle of O_{D} and its vertices are shown by ⊗. Now we prove that the diameter of W_{D} is D. One can also check that all the vertices are at distance at most from the closest vertex of central triangle in W_{D}. Hence the diameter of W_{D} is at most D.

Since |V (O_{D})|= |V (W_{D})|+ the number of isolated vertices, for D=4k+1,k ∈ℕ.

The number of isolated vertices is 9 in the graphs W_{D} for D=4k+1,k∈ℕ. Hence the theorem holds for D=4k+1, k ∈ℕ.

**Case (ii)**

Clearly the maximum degree of the graph W_{D}(which is a sub graph of O_{D}, shown in **Figure 13a** is at most 3. Where the isolated vertices shown in it do not belongs to the vertex set of W_{D}. One can also check that the diameter of the graph W_{D} is D because all the vertices are at distance at most from the closest vertex of central triangle in W_{D}. The vertices of the central triangle of W_{D} are emphasized by ⊗. Hence the theorem holds for D=7.

Now we consider the graphs W_{D} (which are sub graphs of O_{D} for D=4k +7,k∈ℕ) . Such graphs W_{D} for D=11,15,19 depicted in **Figures 13b, 13c and 14**, clearly having degree at most 3. Where the isolated vertices shown in the graphs do not belongs to the vertex set of W_{D}. Note that the central triangle of W_{D} corresponds to the central triangle of O_{D} and its vertices are shown by ⊗. Hence it remains to show that the diameter of W_{D} is D. As can be seen, all the vertices are at distance at most from the closest vertex of central triangle in W_{D}. Hence the diameter of W_{D} is at most D.

Since |V (O_{D})|=|V (W_{D})|+the number of isolated vertices, for D=4k+7,k∈ℕ.

The number of isolated vertices is 9 in the graphs W_{D} for D=4k+7,k∈ℕ. Hence the theorem holds for D=4k+7,k∈ℕ.

Which completes the proof.

Using the fact that N_{G} (Δ−1,D) ≤ N_{G}(Δ,D) for any graph G, we get the following statement [6].

**Corollary 2.4**

Let X be the infinite oxide network. Then

|V (H_{D} )|−(2k+6) ≤ N_{X}(3,D) ≤ |V (H_{D})| for D=4k+8,k ∈ℕ.

|V (O_{D})|−(k+5) ≤ N_{X}(3,D) ≤ |V (O_{D})| for D=4k+6,k∈ℕ.

|V (O_{D})|−9 ≤ N_{X}(3,D) ≤ |V (O_{D})| for D=4k+1,k∈ℕ.

|V (O_{D})|−9 ≤ N_{X}(3,D) ≤ |V (O_{D})| for D=4k+7,k∈ℕ.

#### References

- Bondy A, Murty MR (2008) Graph Theory. Springer.
- Manuel P, Rajasingh I (2011) Minimum Metric Dimension of Silicate Networks.
- Manuel P, Rajasingh I (2009) Topological properties of Silicate Networks. IEEE Xplore.
- Simonraj F, George A (2013) Topological properties of few Poly Oxide, Poly Silicate, DOX and DSL Networks. International Journal of Future Computer and communication 2.
- Holub P, Miller M, Perez-Roses H, Ryan J (2014) Degree Diameter Problem on Honeycomb Networks. Discrete Applied Mathematics 179: 139-151.
- Holub P, Ryan J (2015) Degree Diameter Problem on Triangular Networks. Australasian Journal of Combinatorics 63: 333-345.
- Miller M, Perez-Roses H, Ryan J (2012) The Maximum Degree and Diameter Bounded Sub graph in the Mesh, Discrete Applied Mathematics 160: 1782-1790.
- Xu K, Takahara G, Hassanein H (2006) On the Robustness of Grid-based Deployment in Wireless Sensor Networks. Proceedings of the 2006 international conference on Wireless communications and mobile computing pp:1183-1188.
- Zhang Y, Zhou Y, Fang Y (2005) Key Establishment in sensor networks based on triangular grid deployment model. Military Communications Conference Atlantic City.
- Perez-Roses H, Dekker A, Pineda VG, Watters P (2002) The maximum degree and diameter-bounded sub graph and its applications. Journal of Mathematical Modeling and Algorithms 11: 249-268.
- Miller M, Sira J (2013) Moore graphs and beyond: a survey of the degree/ diameter problem. The Electronic Journal of Combinatorics pp: 1-92.
- Perez-Roses LEH, Pineda VG (2012) Combinatoricswiki.org, updated March 2012.

Citation: Akhtar MS (2018) Degree Diameter Problem on Oxide Networks. J Appl Computat Math 7: 377. Doi: 10.4172/2168-9679.1000377

Copyright: © 2018 Akhtar MS. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.