Degree Diameter Problem on Oxide Network

ISSN: 2168-9679

Journal of Applied & Computational Mathematics

  • Research Article   
  • J Appl Computat Math 7:377, Vol 7(1)
  • DOI: 10.4172/2168-9679.1000377

Degree Diameter Problem on Oxide Network

Akhtar MS*
Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan
*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)=mina∈Ad(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, NG(Δ,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 NG(Δ,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 Sio4 tetrahedra. In chemistry, the corner vertices of sio4 tetrahedron represent oxygen ions and the center vertex represents the silicon ion [2]. In graph theory, the tetrahedra unit sio4 is the complete graph K4. 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 Sio4 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 15n2+3n and the number of edges of SL(n) is 36n2. In Figure 1a, a silicate network of dimension two is shown [2].

applied-computational-mathematics-graph

Figure 1: Graph.

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 9n2+3n and number of edges 18n2 [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 miny∈V(T)dG(x,y) and will be denoted by dG(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 OD is a closed ball of radiusEquation with center as a common vertex m of two triangles with vertex set Equation then

Equation (1)

where k∈N.

Proof

For even D ≥ 4, OD is the closed ball of radius Equation with center as a common vertex of two triangles and Δ=4. Now we draw horizontal lines on the vertices of OD 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 (OD)|=2k+(k+1)+...+(4k−3)+(2k−1)+(4k−1)+2k+(4k +1)+2k+(4k−1)+(2k −1)+...+(2k+3)+(k+1)+2k = 9k2+5k

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

|V (OD)|=(k+1)+(2k+3)+...+(4k−1)+2k+(4k+1)+(2k+1) + (4k+3)+(2k+1)+(4k+1)+2k+(4k−1)+...+(2k+3)+(k+1) = 9k2+13k+5

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

applied-computational-mathematics

Figure 2: OD for D=4 and D=6.

Proposition 1.2

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

OD is a closed ball of radius Equation with center as a triangle with vertex set Equation, where n is the vertex of the central triangle which is closest to x then

Equation (2)

where k∈ℕ

Proof

For odd D>4, OD is the closed ball of radius Equation with center as a triangle and Δ=4. Now we draw horizontal lines on the vertices of OD 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 (OD)|=(2k+2)+(k+1)+...+(4k−2)+(2k−1)+4k+2k+(4k + 2)+(2k+1)+4k+2k+(4k−2)+...+(k+1)+(2k+2) = 9k2+9k+3

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

|V (OD)|=(k+2)+(2k+4)+....+4k+(2k+1)+(4k+2)+(2k+2) + (4k+4)+(2k+1)+(4k+2)+2k+4k+....+(k+1)+(2k+2) = 9k2+18k+9

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

applied-computational-mathematics

Figure 3: OD for D=5 and D=7.

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 HD is obtained by connecting the two oxygen vertices of the closed ball OD with only one vertex of X. Such subgraph HD for D=4 is shown in Figure 4.

applied-computational-mathematics

Figure 4: HD for D=4.

NX(4,D)=|V (HD)|=|V (OD)|+1 for D=4k,k∈ℕ

Case (ii)

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

NX(4,D)=|V (OD)| 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)

NX(Δ,D) ≤ |V (HD)| for D=4k,k∈ℕ.

Case (ii)

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

Values for Δ ≤ 3

Values for Δ=1,2

Since for Δ ≥ Δ(X) we have

NX(Δ,D)=|V (HD)|=|V (OD)|+1 for D=4k,k∈ℕ.And

NX(Δ,D)=|V (OD)| 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 K2.

Hence NX(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 NX(2,D)=2D+1.

Proof

Case (i)

For D=4k,k∈ℕ, clearly the graph HD 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 HD is shown. which implies that For D=4k,k∈ℕ, such a sub graph of HD exist.

applied-computational-mathematics-graphs-having-cycles

Figure 5: Graphs having cycles on 2D+1 vertices.

Case (ii)

For D=4k,k∈ℕ,r∈{1,2,3}, Clearly the graph OD 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 OD 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 OD 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 OD is shown, which implies that For D=4k+r,k∈ℕ,r∈{1,2,3}, such a subgraph of OD 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.

Equation

Proof

Case (i)

Clearly the largest degree of the graphs WD (which are sub graphs of HD, 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 WD. One can also check that the diameter of the graphs WD is D. Hence the theorem holds for D=4,8.

applied-computational-mathematics

Figure 6: WD for D=4,8,12.

Now we consider the graphs WD (which are sub graphs of HD for D=4k+8,k∈ℕ). Such graphs WD 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 WD. Also one can easily check the diameter of WD is D.

applied-computational-mathematics

Figure 7: WD for D=16.

applied-computational-mathematics

Figure 8: WD for D=20.

Since |V(HD)|=|V (WD)|+ the number of isolated vertices, for D=4k+8,k∈ℕ.

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

Case (ii)

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

applied-computational-mathematics

Figure 9: WD for D=6,10,14.

Now we consider the graphs WD (which are sub graphs of OD for D=4k+6,k∈ℕ) clearly having degree at most 3. Such graphs WD 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 WD. Note that the central vertex n of WD corresponds to the central vertex of OD and is depicted by ⊗. Now we prove that the diameter of WD is D. For this we have to prove that Equation for every vertex x of WD. Also one can easily check that all the vertices of WD are at distance at most Equation from the central vertex n. Hence the diameter of WD is at most D. Since |V (OD)|= |V (WD)|+ the number of isolated vertices, for D=4k +6,k∈ℕ.

applied-computational-mathematics

Figure 10: WD for D=18.

The number of isolated vertices form a sequence (k+5) in the graphs WD 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

Equation (5)

and

Equation (6)

Proof:

Case (i)

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

applied-computational-mathematics

Figure 11: WD for D=5,9,13.

applied-computational-mathematics

Figure 12: WD for D=17.

Since |V (OD)|= |V (WD)|+ the number of isolated vertices, for D=4k+1,k ∈ℕ.

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

Case (ii)

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

applied-computational-mathematics

Figure 13: WD for D=7,11,15.

Now we consider the graphs WD (which are sub graphs of OD for D=4k +7,k∈ℕ) . Such graphs WD 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 WD. Note that the central triangle of WD corresponds to the central triangle of OD and its vertices are shown by ⊗. Hence it remains to show that the diameter of WD is D. As can be seen, all the vertices are at distance at most Equation from the closest vertex of central triangle in WD. Hence the diameter of WD is at most D.

applied-computational-mathematics

Figure 14: WD for D=19.

Since |V (OD)|=|V (WD)|+the number of isolated vertices, for D=4k+7,k∈ℕ.

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

Which completes the proof.

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

Corollary 2.4

Let X be the infinite oxide network. Then

|V (HD )|−(2k+6) ≤ NX(3,D) ≤ |V (HD)| for D=4k+8,k ∈ℕ.

|V (OD)|−(k+5) ≤ NX(3,D) ≤ |V (OD)| for D=4k+6,k∈ℕ.

|V (OD)|−9 ≤ NX(3,D) ≤ |V (OD)| for D=4k+1,k∈ℕ.

|V (OD)|−9 ≤ NX(3,D) ≤ |V (OD)| for D=4k+7,k∈ℕ.

References

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.

Select your language of interest to view the total content in your interested language

Post Your Comment Citation
Share This Article
Article Usage
  • Total views: 608
  • [From(publication date): 0-2018 - Aug 21, 2018]
  • Breakdown by view type
  • HTML page views: 569
  • PDF downloads: 39

Post your comment

captcha   Reload  Can't read the image? click here to refresh