# The Vulnerability of Some Networks including Cycles via Domination Parameters

Authors: Tufan Turaci; Hüseyin Aksan
Journal: Journal of Optimization
 (2016)

---

## Abstract

LetG=(V(G),E(G)) be an undirected simple connected graph. A network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. Finding the vulnerability values of communication networks modeled by graphs is important for network designers. The vulnerability value of a communication network shows the resistance of the network after the disruption of some centers or connection lines until a communication breakdown. The domination number and its variations are the most important vulnerability parameters for network vulnerability. Some variations of domination numbers are the 2-domination number, the bondage number, the reinforcement number, the average lower domination number, the average lower 2-domination number, and so forth. In this paper, we study the vulnerability of cycles and related graphs, namely, fans, k-pyramids, and n-gon books, via domination parameters. Then, exact solutions of the domination parameters are obtained for the above-mentioned graphs.


---

## Body

## 1. Introduction

Graph theory has become one of the most powerful mathematical tools in the analysis and study of the architecture of a network. Networks are important structures and appear in many different applications and settings. The study of networks has become an important area of multidisciplinary research involving computer science, mathematics, chemistry, social sciences, informatics, and other theoretical and applied sciences [1–3].It is known that communication systems are often exposed to failures and attacks. So robustness of the network topology is a key aspect in the design of computer networks. The stability of a communication network, composed of processing nodes and communication links, is of prime importance to network designers. As the network begins losing links or nodes, eventually there is a loss in its effectiveness [4]. In the literature, various measures were defined to measure the robustness of network and a variety of graph theoretic parameters have been used to derive formulas to calculate network vulnerability. Graph vulnerability relates to the study of graph when some of its elements (vertices or edges) are removed. The measures of graph vulnerability are usually invariants that measure how the deletion of one or more network elements changes properties of the network [5, 6]. The best known measure of reliability of a graph is its connectivity. The vertex (edge) connectivity is defined to be the minimum number of vertices (edges) whose deletion results in a disconnected or trivial graph [7]. Then the toughness [8], the integrity [9], the domination number [10, 11], the bondage number [12, 13], the 2-domination number [14], and the 2-bondage number [15] have been defined. Moreover, there are many graph theoretical parameters depending upon local damage for the graphs like the average lower independence number [16, 17], the average lower domination number [17, 18], the average connectivity [19], the average lower connectivity [20] and the average lower bondage number [6]. The average parameters have been found to be more useful in some circumstance than the corresponding measures based on worst-case situation [6].A natural way to model the topology of a communications network is as a graph consisting of vertices and edges. In this paper, we consider simple finite undirected graphs by ignoring any variation in the type of edges. LetG=(V(G),E(G)) be a simple undirected graph of order n. We begin by recalling some standard definitions that we need throughout this paper. For any vertex v∈V(G),the open neighborhood of  v is NG(v)={u∈V∣uv∈E(G)} andclosed neighborhood of  v is NG[v]=NG(v)∪{v}. Thedegree of vertex  v in G is denoted by dG(v), that is, the size of its open neighborhood. Themaximum degree of G is max⁡{dG(v)∣v∈V(G)} and theminimum degree of G is min⁡{dG(v)∣v∈V(G)}. The maximum and minimum degrees of a graph G are denoted by ΔG and δG, respectively [11]. The graph G is calledr-regular graph if dG(v)=r for every vertex v∈V(G). The vertex v is called isolated vertex if dG(v)=0. Thenull graph on n-vertices consists of n-isolated vertices with no edges. The join of graphs G and H, denoted by G∨H, is obtained from the disjoint union G+H by adding the edges {vw∣v∈V(G),w∈V(H)} [21]. We will use x and x for the largest integer not larger than x and smallest integer not less than x, respectively.Cycles and various related graphs have been studied for many reasons. Fans, wheels, pyramids, bipyramids, andn-cycle books are among such graphs. The definitions of these graphs will be given in Sections 3.2, 3.3, and 3.4.Our aim in this paper is to consider the computing of the average lower domination number (ALDN) and the average lower 2-domination number (AL2DN) of some networks including cycles. In Section2, definitions and well-known basic results have been given for ALDN and AL2DN, respectively. In Section 3, ALDN and AL2DN of some networks including cycles, namely, fans, k-pyramids, and n-gon books, have been determined.


## 2. The Average Lower Domination Number Parameters and Basic Results

A setS⊆V(G) is adominating set if every vertex in V(G)-S is adjacent to at least one vertex in S. The minimum cardinality taken over alldominating sets of G is called thedomination number of G and it is denoted by γ(G) [10]. Moreover, a2-dominating set of a graph G is a set D⊆V(G) of vertices of graph G such that every vertex of V(G)-D has at least two neighbors in D. The2-domination number of a graph G, denoted by γ2(G), is the minimum cardinality of a2-dominating set of the graph G [2, 11, 14].In 2004, Henning introduced the concept of average domination and average independence [17]. Theaverage lower domination number of a graph G, denoted by γav(G), is defined as γav(G)=1/V(G)∑v∈V(G)γv(G), where thelower domination number, denoted by γv(G), is the minimum cardinality of a dominating set of the graph G that contains the vertex v [17, 18, 22]. In [23], theaverage lower 2-domination number of a graph G was defined. The AL2DN is defined by γ2av(G)=1/V(G)∑v∈V(G)γ2v(G), where thelower 2-domination number, denoted by γ2v(G), of the graph G relative to v is the minimum cardinality of 2-dominating set in the graph G that contains the vertex v. Moreover, Turaci showed that AL2DN is more sensitive than other vulnerability parameters, namely, connectivity, domination number, ALDN, and 2-domination number, in [23].Theorem 1 (see [17]).
For any graph G of ordern with domination number γ(G), γav(G)≤(γ(G)+1)-γ(G)/n, with equality if and only if G has a unique γ(G)-set.Theorem 2 (see [17]).
IfK1,n-1 is a star graph of order n, where n≥3, then γav(K1,n-1)=(2n-1)/n.Theorem 3 (see [17]).
IfPn is a path graph of order n, then(1)γavPn=n+23-23n,ifn≡2mod⁡3;n+23,otherwise.Theorem 4 (see [17]).
IfKn is a complete graph of order n, then γav(Kn)=1.Observation 5.
IfWn is a wheel graph of order n+1, then γav(Wn)=(2n+1)/(n+1).Theorem 6 (see [15]).
IfKn is a complete graph of order n, where n≥2, then γ2(Kn)=2.Theorem 7 (see [15]).
IfPn is a path graph of order n, then γ2(Pn)=n/2+1.Theorem 8 (see [15]).
IfCn is a cycle graph of order n, where n≥3, γ2(Cn)=(n+1)/2.Theorem 9 (see [15]).
IfWn is a wheel graph of order n+1, where n≥5,(2)γ2Wn=2,ifn=3,4;1+n3,otherwise.Theorem 10 (see [23]).
LetG be any connected graph of order n. If γ2(G)-set is unique, then (3)γ2avG=γ2G+1-γ2Gn.Theorem 11 (see [23]).
LetG be any connected graph of order n. If δ(G)≥2, then(4)γ2G≤γ2avG≤γ2G+1-γ2Gn.Theorem 12 (see [23]).
LetG be any connected graph of order n, where n≥2. Then, (5)2≤γ2avG≤n-1+1n.Theorem 13 (see [23]).
LetG and H be two connected graphs of order n and m, respectively. If n≥2 and m≥2, then γ2av(G)+γ2av(H)≥γ2av(G+H).Theorem 14 (see [23]).
LetT be any connected tree of order n. If T has s support vertices and (n-s) leaf vertices, then γ2av(T)≥n-s+s/n.Theorem 15 (see [23]).
IfPn is a path graph of order n, then(6)γ2avPn=n2+2-n/2+1n,ifnisodd;n2+1,ifnis  even.Theorem 16 (see [23]).
IfWn is a wheel graph of order n+1, where n≥5, then(7)γ2avWn=1+n3.Theorem 17 (see [23]).
IfKn is a complete graph of order n, where n≥2, then γ2av(Kn)=2.Theorem 18 (see [23]).
IfK1,n-1 is a star graph of order n, where n≥3, then(8)γ2avK1,n-1=n-1+1n.


## 3. Calculation of ALDN and AL2DN of Cycles and Related Networks

### 3.1. Cycles

Theorem 19 (see [17]).
IfCn is a cycle graph of order n, then γav(Cn)=2.Theorem 20 (see [23]).
IfCn is a cycle graph of order n, then γ2av(Cn)=(n+1)/2.


### 3.2. Fans

Definition 21 (see [21]).
If one joins a vertex ofCn(n≥3) to all other vertices, the resulting graph is called afan (also known as ashell), denoted by Fn. For n=3, we notice that F3≡C3. Fans can be described by the join operation Fn=Pn-1+v, where n≥3. There is a vertex with (n-1)-degree, namely, u, in the graph Fn.Theorem 22.
LetFn be a fan of order n and n≥5; then γ2(Fn)=(n+2)/3.Proof.
The 2-dominating set is formed by two ways inFn.
Case  1. Let D1 be a 2-dominating set and let D1 include the vertex u. So, the vertex u dominates vertices of V(Fn)-{u} by once. Clearly, these (n-1)-vertices which are dominated once form the path Pn-1. Due to the fact that γ(Pn-1)=(n-1)/3, these (n-1)/3 vertices must be taken to the set D1. So, D1=1+(n-1)/3=(n+2)/3 is obtained.
Case  2. Let D2 be a 2-dominating set and let D2 not include vertex u. So, the set D2 must include vertices of subgraph path Pn-1. By Theorem 7, we have D2=1+(n-1)/2=(n+1)/2.
By Cases  1 and 2,D2≥D1 is obtained for n≥5. As a result, we get γ2(Fn)=(n+2)/3.Theorem 23.
LetFn be a fan of order n and n≥3; then γav(Fn)=(2n-1)/n.Proof.
By the definition of domination number and the structure ofFn, the dominating set of Fn is unique and γ(Fn)=1. By Theorem 1, we get γav(Fn)=1+1-1/n=(2n-1)/n.Theorem 24.
LetFn be a fan of order n and n≥5; then (9)γ2avFn=1nn+23+n-1γavPn-1+1.Proof.
Whenγ2v(Fn) is calculated for all vertices in Fn, the vertices in three cases should be examined.
Case  1. For the vertex u, the 2-dominating set must include the vertex u by Theorem 22. The rest of the proof of this case is similar to Case  1 of Theorem 22. So, we get γ2u(Fn)=1+(n-1)/3=(n+2)/3.
Case  2. For all vertices vi∈V(Fn)-u which forms the graph Pn-1. We know that ∑i=1n-1γvi(Fn)=(n-1)γav(Pn-1) by the definition of ALDN. Furthermore, we know that the vertex u must be in the 2-dominating set. So, we have ∑i=1n-1γ2vi=(n-1)γav(Pn-1)+(n-1) for the sum of the lower 2-domination number of all vertices vi∈V(Fn)-u. As a result, ∑i=1n-1γ2vi(Fn)=(n-1)(γav(Pn-1)+1) is obtained.
By Cases  1 and 2, we get(10)γ2avFn=1VFnγ2uFn+∑i=1n-1γ2viFn=1nn+23+n-1γavPn-1+1.Remark 25.
LetFn be a fan of order n and n≥5; then(11)γ2avFn=n2+3n-3/3+n-1/3n,ifn≡0mod⁡3;n2+3n-1/3+n-1/3n,otherwise.Proof.
This is clear from Theorems3 and 24.


### 3.3.k-Pyramids

Definition 26 (see [21]).
The join graphCn∨Nk(n≥3,k≥1), where Nk is the null graph of order k, is called a k-pyramid and is denoted by kP(n). The 2-pyramid Cn∨N2 is called bipyramid and is denoted by BP(n). The 1-pyramid Cn∨N1 is the wheel graph Wn.Theorem 27.
LetBP(n) be a bipyramid of order n+2 and n≥7; then γ(BP(n))=2.Proof.
BecauseΔ(BP(n))<n+1, the domination number γ(BP(n)) is greater than 1. Let v1 and v2 be vertices whose degrees are n, and let D be a dominating set. The dominating set D is formed by 3 cases.
Case  1. Let v1,v2∈D. Due to NBP(n)v1,v2=V(BP(n)), the set D is a dominating set.
Case  2. Let v1∈D and let ui be any vertex of Cn. Due to the fact that NBP(n)v1,ui=V(BP(n)), the set D is a dominating set.
Case  3. Let v1,v2∉D. Then, the set D includes only vertices of Cn. So, we have D≥n/3.
By Cases  1, 2, and 3,γ(BP(n))=2 is obtained.Theorem 28.
LetBP(n) be a bipyramid of order n+2 and n≥7; then(12)γavBPn=2.Proof.
Whenγv(BP(n)) is calculated for all vertices in the graph BP(n), the vertices in two cases should be examined. Let v1 and v2 be vertices whose degrees are n.
Case  1. For the vertices v1 and v2, we know that the set {v1,v2} dominates all vertices of V(BP(n))-{v1,v2}. So, we get γv1(BP(n))=γv2(BP(n))=2.
Case  2. For all vertices vi∈V(BP(n))-v1,v2, by the definition of lower domination number and Case  2 of Theorem 27, we have γvi(BP(n))=2 for all vertices vi∈V(BP(n))-v1,v2.
By Cases  1 and 2, we getγav(BP(n))=2.Theorem 29.
LetBP(n) be a bipyramid of order n+2 and n≥3; then γ2(BP(n))=2. Furthermore, the 2-dominating set of BP(n) is unique.Proof.
Letui be the vertices of Cn, where 1≤i≤n, and let vj be vertices of the graph K2¯, where 1≤j≤2. There are 3 cases while forming 2-dominating set.
Case  1. Let D1 be a 2-dominating set of BP(n). Furthermore, the set D1 contains vertices v1 and v2. Clearly, NBP(n)[v1,v2]=V(BP(n)). So, D1=2 is obtained.
Case  2. Let D2 be any 2-dominating set, and the set D2 contains v1or v2. So, the set D2 1-dominates all vertices of Cn. By the definition of γ(Cn), if we add n/3 vertices to the set D2, then all of Cn graph’s vertices are 2-dominated. So, n/3≥2 for n≥5. Hence, D2=1+n/3 is obtained.
Case  3. Let D3 be any 2-dominating set. Moreover, the set D3 contains only vertices ui of Cn. It is clear that the set D3 is the 2-dominating set of Cn. By Theorem 8, we have D3=(n+1)/2.
By Cases  1, 2, and 3 we getD1=2, D2≥3, and D3≥3 for n≥5. As a result, by the definition of 2-domination number, we have γ2(BP(n))=2 and this 2-dominating set is unique.Theorem 30.
LetBP(n) be a bipyramid of order n+2 and n≥3; then (13)γ2avBPn=3n+4n+2.Proof.
Since the 2-dominating set is unique, we haveγ2av(BP(n))=2+1-2/(n+2)=(3n+4)/(n+2) by Theorem 10.Theorem 31.
For the 3-pyramid3P(n) with n≥7, γ2(3P(n))=3.Proof.
There are 3 vertices whose degrees aren in the graph 3P(n) and they are shown by u1, u2, and u3. We have four cases while 2-dominating set is forming.
Case  1. Let D1 be any 2-dominating set of 3P(n) and let D1 contain vertices u1, u2, and u3. It is clear that N3P(n)[u1,u2,u3]=V(3P(n)) is obtained. So, the set D1 is 2-dominating set of 3P(n). Thus, D1=3 is obtained.
Case  2. Let D2 be any 2-dominating set of 3P(n) and let set D2 include any two vertices of the vertices u1, u2, and u3. These two vertices are 2-dominated by the vertices of Cn. If the remaining vertex is added to D2 set, it is similar to set D1 and all vertices of 3P(n) are 2-dominated. If the remaining vertex is not added to D2 set, two vertices of V(3P(n))-{u1,u2,u3} must be added to the set D2. Thus, D2≥ 3 is obtained.
Case  3. Let D3 be any 2-dominating set of 3P(n) and let the set D3 include any one vertex of u1, u2, and u3. So, the vertices of Cn are dominated once by the set D3. Since the set D3 does not include the remaining two vertices of the vertices u1, u2, and u3, n/3 vertices of Cn must be taken to set D3 to 2-dominate all vertices of Cn and the remaining two vertices of the vertices u1, u2, and u3. Because n≥7, we have D3=n/3+1.
Case  4. Let D4 be any 2-dominating set of 3P(n) and let the set D4 not include any vertices of u1, u2, and u3. So, we must add vertices of the graph Cn to set D4. We know that γ2(Cn)=(n+1)/2 by Theorem 8. Thus, D4≥(n+1)/2 is obtained.
By Cases  1, 2, 3, and 4 we getD1=3, D2≥3, D3≥n/3+1, and D4≥(n+1)/2 for n≥7. As a result we have γ2(3P(n))=3 by the definition of 2-domination number and this 2-dominating set is unique.Theorem 32.
For the 3-pyramid3P(n) with n≥7, γ2av(3P(n))=(4n+9)/(n+3).Proof.
Since the 2-dominating set is unique, we haveγ2av(3P(n))=3+1-3/(n+3)=(4n+9)/(n+3) by Theorem 10.Theorem 33.
LetkP(n) be a k-pyramid with k≥4 and n≥7; then γ2(kP(n))=4.Proof.
The vertices ofCn are denoted by vi, where i∈{1,…,n}, and the remaining k-vertices are denoted by uj, where j∈{1,…,k}. We have three cases while 2-dominating set is forming.
Case  1. Let D1 be any 2-dominating set of the graph kP(n) and let D1 contain only vertices uj, where j∈{1,…,k}. It is clear that set u1,u2…,uj 2-dominated all vertices of kP(n). So, D1=k and D1≥4 are obtained.
Case  2. Let D2 be any 2-dominating set of kP(n) and let D2 contain only vertices of vi, where i∈{1,…,n}. By Theorem 8, we have D2=(n+1)/2. As a result, D2≥4 is obtained.
Case  3. Let D3 be any 2-dominating set of kP(n) and let D3 contain any vertex of uj and vi, where j∈{1,…,k} and i∈{1,…,n}. Let D3=u1,v1. Let ={uj∣1≤j≤k}. The vertex u1 dominates vertices of V(Cn)-u1 by once and the vertex v1 dominates vertices of U-v1 by once. If any vertex of vi and any vertex of uj are added to set D3, then D3 will be 2-dominating set of the graph kP(n). Hence, D3=4 is obtained.
By Cases  1, 2, and 3 we getD1≥4, D2≥4, and D3=4 for n≥7. As a result, by the definition of 2-domination number, we have γ2(kP(n))=4.Theorem 34.
LetkP(n) be a k-pyramid with k≥4 and n≥7; then γ2av(kP(n))=4.Proof.
By Theorem33, we have the lower 2-domination number as 4 for all vertices of kP(n). Thus, γ2av(kP(n))=4 is obtained.


### 3.4.n-Gon Books

Definition 35 (see [21]).
Whenk copies of Cn(n≥3) share a common edge, they will form an n-gon book of  kpages and are denoted by B(n,k). The degree set of B(n,k) is {2,k+1}. Therefore, the vertices of B(n,k) are of two kinds: vertices of degree 2, which will be referred to asminor vertices, and vertices of degree k+1, which will be referred to asmajor vertices. The minor vertices of B(n,k) are labeled v11,v12…,v1j,v21,v22,…,v2j,…,vk1,vk2,…,vkj, that is vij, where i∈{1,…,k} and j∈{1,…,n-2}.Theorem 36.
LetB(n,k) be an n-gon book and n≥5; then(14)γBn,k=kn-43+2,n≡1mod⁡3;kn-33+1,otherwise.Proof.
Letu1 and u2 be two major vertices. We have three cases depending on the dominating set of B(n,k) that are including major vertices or not.
Case  1. Let D1 be a dominating set, and let D1 include two major vertices. The set {u1,u2} dominates 2k-vertices from all Cn. So, there are (n-4)-vertices which are not dominated from each Cn. Then the k-distinct path Pn-4 is obtained by these minor vertices. Thus, |D1|=k(n-4)/3+2 is obtained.
Case  2. Let D2 be a dominating set, and let u1∈D2 (or u2∈D2). The vertex u1 dominates the vertex u2 and k-vertices which are adjacent to the vertex u1 from all Cn. Then the remaining (n-3)-vertices are not dominated from each Cn. So, the k-distinct path Pn-3 is obtained by these minor vertices. As a result, |D2|=k(n-4)/3+1 is obtained.
Case  3. Let D3 be a dominating set, and let {u1,u2}∉D3. Since the set D3 includes only minor vertices, we have two subcases depending on n.
Case  3.1. Let n≡0,1(mod⁡3). Due to the structure of B(n,k), the set D3 must include (n-2)/3-vertices from each Cn. So, the whole vertices of B(n,k) are dominated. As a result we have |D3|=k(n-2)/3.
Case  3.2. Let n≡2(mod⁡3). Due to the structure of B(n,k), two minor vertices which are neighbors to the major vertices must be taken to the set D3 from any graph Cn. Furthermore, the remaining (k-1)(n-2)-vertices are not dominated in the graph B(n,k). Since (k-1)(n-2)/3-vertices must be taken to the set D3, D3=2+(n-6)/3+(k-1)(n-2)/3 is obtained.
By Cases  3.1 and 3.2, we get(15)D3=2+n-63+k-1·n-23,n≡2mod⁡3;k·n-23,otherwise.Clearly, if n≡0(mod⁡3), then we have D3>D1>D2, if n≡1(mod⁡3), then we have D2>D3>D1, and if n≡2(mod⁡3), then we have D1>D3=D2. As a result, we get(16)γBn,k=kn-43+2,n≡1mod⁡3;kn-33+1,otherwise.Thus the proof is completed.Theorem 37.
LetB(n,k) be an n-gon book and n≥5; then(17)γavBn,k=kn-33+1,ifn≡2mod⁡3;3+kn-43-2+kn-4/3kn-2+2,ifn≡1mod⁡3;1kn-2+2n-2k+2-kn31+kn-33+kn32+kn-33,ifn≡0mod⁡3.Proof.
While finding lower domination number of all vertices ofB(n,k), we have three cases depending on n.
Case  1. Let n≡1(mod⁡3), and let D be a dominating set. Clearly, the set D is a unique dominating set. By Theorem 10, we have (18)γavBn,k=3+kn-43-2+kn-4/3kn-2+2.
Case  2. Let n≡2(mod⁡3), and let D be a dominating set. By Theorem 36, the set D is formed by two ways. Clearly, γvi(B(n,k))=(n-3)/3+1 is obtained for every vi∈V(B(n,k)). As a result, we have γav(B(n,k))=1+k(n-3)/3.
Case  3. Let n≡0(mod⁡3), and let D be a dominating set. By Case  2 of Theorem 36, we know that the set D includes either the vertex u1 or the vertex u2. Let S={vij∣i∈{1,…,k}∧j∈{1,4,…,n-2}}. Clearly, the set D contains vertices of V(B(n,k))-S by Theorem 36. Thus, we have γvi(B(n,k))=1+k(n-3)/3 for every vi∈V(B(n,k))-S. Furthermore, we have γvi∗(B(n,k))=2+k(n-3)/3 for every vi∗∈S. Thus,(19)γavBn,k=1VBn,k∑vi∈VBn,k-SγviBn,k+∑vi∗∈Sγvi∗Bn,k=1kn-2+2n-2k+2-kn31+kn-33+kn32+kn-33.
By Cases  1, 2, and 3 the proof is completed.Theorem 38.
LetB(n,k) be an n-gon book and n≥5; then(20)γ2Bn,k=kn+12-1+1,ifniseven;kn-42+1+2,ifnisodd.Proof.
Letu1 and u2 be two major vertices. We have two cases depending on n.
Case  1. Let n be even, and let D be 2-dominating set. We know that the set D contains either the vertex u1 or the vertex u2 by the definition of B(n,k) and Theorem 8. Thus, (n+1)/2-1-vertices of each Cn must be taken to the set D. Since there is k-graph Cn, we have D=k(n+1)/2-1+1. So, γ2(B(n,k))=k(n+1)/2-1+1 is obtained.
Case  2. Let n be odd. We have two subcases depending on the 2-dominating set of B(n,k) that are including major vertices or not.
Case  2.1. Let D1 be 2-dominating set, and let D1 include any major vertex. Clearly, the set D must include two major vertices in this subcase by Theorem 8. So, the set {u1,u2} dominates 2k-vertices from all Cn. Then, (n-4)-vertices are not dominated from each Cn. Thus, the k-distinct path Pn-4 is obtained by these minor vertices. As a result, |D1|=k(n-4)/2+1+2 is obtained.
Case  2.2. Let D2 be 2-dominating set, and let {u1,u2}∉D2. Clearly, the set D2 includes (n-2)/2+1-vertices of V(Cn)-{u1,u2} of each Cn by Theorem 7. Thus, |D2|=k(n-2)/2+1 is obtained.
By Cases  2.1 and 2.2|D1|=|D2| for k=2 and n≥5. Then we have |D1|<|D2| for k≥3 and n≥5. Furthermore, 2-dominating set is unique for k≥3 and n≥5. As a result, γ2(B(n,k))=k(n-4)/2+1+2 is obtained.
By Cases  1 and 2, the proof is completed.Theorem 39.
LetB(n,k) be an n-gon book, where n≥3 and k≥3; then(21)γ2avBn,k=kn+12-1+1,ifniseven;kn-42+1+3-kn-4/2+1+2kn-2+2,ifnisodd.Proof.
Letu1 and u2 be two major vertices. We have two cases depending on n.
Case  1. Let n be even. We have that the 2-dominating set including the vertex u1 is 2-dominating set of any Cn. Since the vertex u1 is common vertex of each Cn and by Theorem 8, we get γ2u1(B(n,k))=k(n+1)/2-1+1. Similarly, we get γ2u2(B(n,k))=k(n+1)/2-1+1. Let vi1 be minor vertex which is neighbor to the vertex u1 of any Cn, and let vi(n-2) be minor vertex which is neighbor to the vertex u2 in the same graph Cn. It is easy to see that the 2-dominating set including the vertex vi1 is the 2-dominating set including the vertex u2 by Theorem 8. Similarly, the 2-dominating set including the vertex vi(n-2) is the 2-dominating set including the vertex u1. Thus, γ2vi1(B(n,k))=γ2vi(n-2)(B(n,k))=k(n+1)/2-1+1 is obtained. Furthermore, we get γ2vij(B(n,k))=k(n+1)/2-1+1 for every vij∈V(B(n,k))-{u1,u2}, where i∈{1,…,k} and j∈{1,…,n-2}. As a result, γ2av(B(n,k))=k(n+1)/2-1+1 is obtained.
Case  2. Let n be odd. We have two subcases depending on k.
Case  2.1. Let k=2. We know that 2-dominating set is formed by two ways in Case  2 of Theorem 38. Clearly, γ2v(B(n,k))=k(n-4)/2+1+2 is obtained for every vertex v∈V(B(n,k)). As a result, γ2av(B(n,k))=k(n-4)/2+1+2 is obtained.
Case  2.2. Let k≥3. We know that 2-dominating set is unique by Case  2 of Theorem 38. So, γ2av(B(n,k))=k(n-4)/2+1+3-k(n-4)/2+1+2/k(n-2)+2 is obtained by Theorem 10.
By Cases  1 and 2 the proof is completed.Theorem 40.
LetB(n,k) be an n-gon book, where n≥3 and k=2; then(22)γ2avBn,k=kn+12-1+1,ifniseven;kn-42+1+2,ifnisodd.Proof.
The proof directly comes from Theorem39.


## 3.1. Cycles

Theorem 19 (see [17]).
IfCn is a cycle graph of order n, then γav(Cn)=2.Theorem 20 (see [23]).
IfCn is a cycle graph of order n, then γ2av(Cn)=(n+1)/2.


## 3.2. Fans

Definition 21 (see [21]).
If one joins a vertex ofCn(n≥3) to all other vertices, the resulting graph is called afan (also known as ashell), denoted by Fn. For n=3, we notice that F3≡C3. Fans can be described by the join operation Fn=Pn-1+v, where n≥3. There is a vertex with (n-1)-degree, namely, u, in the graph Fn.Theorem 22.
LetFn be a fan of order n and n≥5; then γ2(Fn)=(n+2)/3.Proof.
The 2-dominating set is formed by two ways inFn.
Case  1. Let D1 be a 2-dominating set and let D1 include the vertex u. So, the vertex u dominates vertices of V(Fn)-{u} by once. Clearly, these (n-1)-vertices which are dominated once form the path Pn-1. Due to the fact that γ(Pn-1)=(n-1)/3, these (n-1)/3 vertices must be taken to the set D1. So, D1=1+(n-1)/3=(n+2)/3 is obtained.
Case  2. Let D2 be a 2-dominating set and let D2 not include vertex u. So, the set D2 must include vertices of subgraph path Pn-1. By Theorem 7, we have D2=1+(n-1)/2=(n+1)/2.
By Cases  1 and 2,D2≥D1 is obtained for n≥5. As a result, we get γ2(Fn)=(n+2)/3.Theorem 23.
LetFn be a fan of order n and n≥3; then γav(Fn)=(2n-1)/n.Proof.
By the definition of domination number and the structure ofFn, the dominating set of Fn is unique and γ(Fn)=1. By Theorem 1, we get γav(Fn)=1+1-1/n=(2n-1)/n.Theorem 24.
LetFn be a fan of order n and n≥5; then (9)γ2avFn=1nn+23+n-1γavPn-1+1.Proof.
Whenγ2v(Fn) is calculated for all vertices in Fn, the vertices in three cases should be examined.
Case  1. For the vertex u, the 2-dominating set must include the vertex u by Theorem 22. The rest of the proof of this case is similar to Case  1 of Theorem 22. So, we get γ2u(Fn)=1+(n-1)/3=(n+2)/3.
Case  2. For all vertices vi∈V(Fn)-u which forms the graph Pn-1. We know that ∑i=1n-1γvi(Fn)=(n-1)γav(Pn-1) by the definition of ALDN. Furthermore, we know that the vertex u must be in the 2-dominating set. So, we have ∑i=1n-1γ2vi=(n-1)γav(Pn-1)+(n-1) for the sum of the lower 2-domination number of all vertices vi∈V(Fn)-u. As a result, ∑i=1n-1γ2vi(Fn)=(n-1)(γav(Pn-1)+1) is obtained.
By Cases  1 and 2, we get(10)γ2avFn=1VFnγ2uFn+∑i=1n-1γ2viFn=1nn+23+n-1γavPn-1+1.Remark 25.
LetFn be a fan of order n and n≥5; then(11)γ2avFn=n2+3n-3/3+n-1/3n,ifn≡0mod⁡3;n2+3n-1/3+n-1/3n,otherwise.Proof.
This is clear from Theorems3 and 24.


## 3.3.k-Pyramids

Definition 26 (see [21]).
The join graphCn∨Nk(n≥3,k≥1), where Nk is the null graph of order k, is called a k-pyramid and is denoted by kP(n). The 2-pyramid Cn∨N2 is called bipyramid and is denoted by BP(n). The 1-pyramid Cn∨N1 is the wheel graph Wn.Theorem 27.
LetBP(n) be a bipyramid of order n+2 and n≥7; then γ(BP(n))=2.Proof.
BecauseΔ(BP(n))<n+1, the domination number γ(BP(n)) is greater than 1. Let v1 and v2 be vertices whose degrees are n, and let D be a dominating set. The dominating set D is formed by 3 cases.
Case  1. Let v1,v2∈D. Due to NBP(n)v1,v2=V(BP(n)), the set D is a dominating set.
Case  2. Let v1∈D and let ui be any vertex of Cn. Due to the fact that NBP(n)v1,ui=V(BP(n)), the set D is a dominating set.
Case  3. Let v1,v2∉D. Then, the set D includes only vertices of Cn. So, we have D≥n/3.
By Cases  1, 2, and 3,γ(BP(n))=2 is obtained.Theorem 28.
LetBP(n) be a bipyramid of order n+2 and n≥7; then(12)γavBPn=2.Proof.
Whenγv(BP(n)) is calculated for all vertices in the graph BP(n), the vertices in two cases should be examined. Let v1 and v2 be vertices whose degrees are n.
Case  1. For the vertices v1 and v2, we know that the set {v1,v2} dominates all vertices of V(BP(n))-{v1,v2}. So, we get γv1(BP(n))=γv2(BP(n))=2.
Case  2. For all vertices vi∈V(BP(n))-v1,v2, by the definition of lower domination number and Case  2 of Theorem 27, we have γvi(BP(n))=2 for all vertices vi∈V(BP(n))-v1,v2.
By Cases  1 and 2, we getγav(BP(n))=2.Theorem 29.
LetBP(n) be a bipyramid of order n+2 and n≥3; then γ2(BP(n))=2. Furthermore, the 2-dominating set of BP(n) is unique.Proof.
Letui be the vertices of Cn, where 1≤i≤n, and let vj be vertices of the graph K2¯, where 1≤j≤2. There are 3 cases while forming 2-dominating set.
Case  1. Let D1 be a 2-dominating set of BP(n). Furthermore, the set D1 contains vertices v1 and v2. Clearly, NBP(n)[v1,v2]=V(BP(n)). So, D1=2 is obtained.
Case  2. Let D2 be any 2-dominating set, and the set D2 contains v1or v2. So, the set D2 1-dominates all vertices of Cn. By the definition of γ(Cn), if we add n/3 vertices to the set D2, then all of Cn graph’s vertices are 2-dominated. So, n/3≥2 for n≥5. Hence, D2=1+n/3 is obtained.
Case  3. Let D3 be any 2-dominating set. Moreover, the set D3 contains only vertices ui of Cn. It is clear that the set D3 is the 2-dominating set of Cn. By Theorem 8, we have D3=(n+1)/2.
By Cases  1, 2, and 3 we getD1=2, D2≥3, and D3≥3 for n≥5. As a result, by the definition of 2-domination number, we have γ2(BP(n))=2 and this 2-dominating set is unique.Theorem 30.
LetBP(n) be a bipyramid of order n+2 and n≥3; then (13)γ2avBPn=3n+4n+2.Proof.
Since the 2-dominating set is unique, we haveγ2av(BP(n))=2+1-2/(n+2)=(3n+4)/(n+2) by Theorem 10.Theorem 31.
For the 3-pyramid3P(n) with n≥7, γ2(3P(n))=3.Proof.
There are 3 vertices whose degrees aren in the graph 3P(n) and they are shown by u1, u2, and u3. We have four cases while 2-dominating set is forming.
Case  1. Let D1 be any 2-dominating set of 3P(n) and let D1 contain vertices u1, u2, and u3. It is clear that N3P(n)[u1,u2,u3]=V(3P(n)) is obtained. So, the set D1 is 2-dominating set of 3P(n). Thus, D1=3 is obtained.
Case  2. Let D2 be any 2-dominating set of 3P(n) and let set D2 include any two vertices of the vertices u1, u2, and u3. These two vertices are 2-dominated by the vertices of Cn. If the remaining vertex is added to D2 set, it is similar to set D1 and all vertices of 3P(n) are 2-dominated. If the remaining vertex is not added to D2 set, two vertices of V(3P(n))-{u1,u2,u3} must be added to the set D2. Thus, D2≥ 3 is obtained.
Case  3. Let D3 be any 2-dominating set of 3P(n) and let the set D3 include any one vertex of u1, u2, and u3. So, the vertices of Cn are dominated once by the set D3. Since the set D3 does not include the remaining two vertices of the vertices u1, u2, and u3, n/3 vertices of Cn must be taken to set D3 to 2-dominate all vertices of Cn and the remaining two vertices of the vertices u1, u2, and u3. Because n≥7, we have D3=n/3+1.
Case  4. Let D4 be any 2-dominating set of 3P(n) and let the set D4 not include any vertices of u1, u2, and u3. So, we must add vertices of the graph Cn to set D4. We know that γ2(Cn)=(n+1)/2 by Theorem 8. Thus, D4≥(n+1)/2 is obtained.
By Cases  1, 2, 3, and 4 we getD1=3, D2≥3, D3≥n/3+1, and D4≥(n+1)/2 for n≥7. As a result we have γ2(3P(n))=3 by the definition of 2-domination number and this 2-dominating set is unique.Theorem 32.
For the 3-pyramid3P(n) with n≥7, γ2av(3P(n))=(4n+9)/(n+3).Proof.
Since the 2-dominating set is unique, we haveγ2av(3P(n))=3+1-3/(n+3)=(4n+9)/(n+3) by Theorem 10.Theorem 33.
LetkP(n) be a k-pyramid with k≥4 and n≥7; then γ2(kP(n))=4.Proof.
The vertices ofCn are denoted by vi, where i∈{1,…,n}, and the remaining k-vertices are denoted by uj, where j∈{1,…,k}. We have three cases while 2-dominating set is forming.
Case  1. Let D1 be any 2-dominating set of the graph kP(n) and let D1 contain only vertices uj, where j∈{1,…,k}. It is clear that set u1,u2…,uj 2-dominated all vertices of kP(n). So, D1=k and D1≥4 are obtained.
Case  2. Let D2 be any 2-dominating set of kP(n) and let D2 contain only vertices of vi, where i∈{1,…,n}. By Theorem 8, we have D2=(n+1)/2. As a result, D2≥4 is obtained.
Case  3. Let D3 be any 2-dominating set of kP(n) and let D3 contain any vertex of uj and vi, where j∈{1,…,k} and i∈{1,…,n}. Let D3=u1,v1. Let ={uj∣1≤j≤k}. The vertex u1 dominates vertices of V(Cn)-u1 by once and the vertex v1 dominates vertices of U-v1 by once. If any vertex of vi and any vertex of uj are added to set D3, then D3 will be 2-dominating set of the graph kP(n). Hence, D3=4 is obtained.
By Cases  1, 2, and 3 we getD1≥4, D2≥4, and D3=4 for n≥7. As a result, by the definition of 2-domination number, we have γ2(kP(n))=4.Theorem 34.
LetkP(n) be a k-pyramid with k≥4 and n≥7; then γ2av(kP(n))=4.Proof.
By Theorem33, we have the lower 2-domination number as 4 for all vertices of kP(n). Thus, γ2av(kP(n))=4 is obtained.


## 3.4.n-Gon Books

Definition 35 (see [21]).
Whenk copies of Cn(n≥3) share a common edge, they will form an n-gon book of  kpages and are denoted by B(n,k). The degree set of B(n,k) is {2,k+1}. Therefore, the vertices of B(n,k) are of two kinds: vertices of degree 2, which will be referred to asminor vertices, and vertices of degree k+1, which will be referred to asmajor vertices. The minor vertices of B(n,k) are labeled v11,v12…,v1j,v21,v22,…,v2j,…,vk1,vk2,…,vkj, that is vij, where i∈{1,…,k} and j∈{1,…,n-2}.Theorem 36.
LetB(n,k) be an n-gon book and n≥5; then(14)γBn,k=kn-43+2,n≡1mod⁡3;kn-33+1,otherwise.Proof.
Letu1 and u2 be two major vertices. We have three cases depending on the dominating set of B(n,k) that are including major vertices or not.
Case  1. Let D1 be a dominating set, and let D1 include two major vertices. The set {u1,u2} dominates 2k-vertices from all Cn. So, there are (n-4)-vertices which are not dominated from each Cn. Then the k-distinct path Pn-4 is obtained by these minor vertices. Thus, |D1|=k(n-4)/3+2 is obtained.
Case  2. Let D2 be a dominating set, and let u1∈D2 (or u2∈D2). The vertex u1 dominates the vertex u2 and k-vertices which are adjacent to the vertex u1 from all Cn. Then the remaining (n-3)-vertices are not dominated from each Cn. So, the k-distinct path Pn-3 is obtained by these minor vertices. As a result, |D2|=k(n-4)/3+1 is obtained.
Case  3. Let D3 be a dominating set, and let {u1,u2}∉D3. Since the set D3 includes only minor vertices, we have two subcases depending on n.
Case  3.1. Let n≡0,1(mod⁡3). Due to the structure of B(n,k), the set D3 must include (n-2)/3-vertices from each Cn. So, the whole vertices of B(n,k) are dominated. As a result we have |D3|=k(n-2)/3.
Case  3.2. Let n≡2(mod⁡3). Due to the structure of B(n,k), two minor vertices which are neighbors to the major vertices must be taken to the set D3 from any graph Cn. Furthermore, the remaining (k-1)(n-2)-vertices are not dominated in the graph B(n,k). Since (k-1)(n-2)/3-vertices must be taken to the set D3, D3=2+(n-6)/3+(k-1)(n-2)/3 is obtained.
By Cases  3.1 and 3.2, we get(15)D3=2+n-63+k-1·n-23,n≡2mod⁡3;k·n-23,otherwise.Clearly, if n≡0(mod⁡3), then we have D3>D1>D2, if n≡1(mod⁡3), then we have D2>D3>D1, and if n≡2(mod⁡3), then we have D1>D3=D2. As a result, we get(16)γBn,k=kn-43+2,n≡1mod⁡3;kn-33+1,otherwise.Thus the proof is completed.Theorem 37.
LetB(n,k) be an n-gon book and n≥5; then(17)γavBn,k=kn-33+1,ifn≡2mod⁡3;3+kn-43-2+kn-4/3kn-2+2,ifn≡1mod⁡3;1kn-2+2n-2k+2-kn31+kn-33+kn32+kn-33,ifn≡0mod⁡3.Proof.
While finding lower domination number of all vertices ofB(n,k), we have three cases depending on n.
Case  1. Let n≡1(mod⁡3), and let D be a dominating set. Clearly, the set D is a unique dominating set. By Theorem 10, we have (18)γavBn,k=3+kn-43-2+kn-4/3kn-2+2.
Case  2. Let n≡2(mod⁡3), and let D be a dominating set. By Theorem 36, the set D is formed by two ways. Clearly, γvi(B(n,k))=(n-3)/3+1 is obtained for every vi∈V(B(n,k)). As a result, we have γav(B(n,k))=1+k(n-3)/3.
Case  3. Let n≡0(mod⁡3), and let D be a dominating set. By Case  2 of Theorem 36, we know that the set D includes either the vertex u1 or the vertex u2. Let S={vij∣i∈{1,…,k}∧j∈{1,4,…,n-2}}. Clearly, the set D contains vertices of V(B(n,k))-S by Theorem 36. Thus, we have γvi(B(n,k))=1+k(n-3)/3 for every vi∈V(B(n,k))-S. Furthermore, we have γvi∗(B(n,k))=2+k(n-3)/3 for every vi∗∈S. Thus,(19)γavBn,k=1VBn,k∑vi∈VBn,k-SγviBn,k+∑vi∗∈Sγvi∗Bn,k=1kn-2+2n-2k+2-kn31+kn-33+kn32+kn-33.
By Cases  1, 2, and 3 the proof is completed.Theorem 38.
LetB(n,k) be an n-gon book and n≥5; then(20)γ2Bn,k=kn+12-1+1,ifniseven;kn-42+1+2,ifnisodd.Proof.
Letu1 and u2 be two major vertices. We have two cases depending on n.
Case  1. Let n be even, and let D be 2-dominating set. We know that the set D contains either the vertex u1 or the vertex u2 by the definition of B(n,k) and Theorem 8. Thus, (n+1)/2-1-vertices of each Cn must be taken to the set D. Since there is k-graph Cn, we have D=k(n+1)/2-1+1. So, γ2(B(n,k))=k(n+1)/2-1+1 is obtained.
Case  2. Let n be odd. We have two subcases depending on the 2-dominating set of B(n,k) that are including major vertices or not.
Case  2.1. Let D1 be 2-dominating set, and let D1 include any major vertex. Clearly, the set D must include two major vertices in this subcase by Theorem 8. So, the set {u1,u2} dominates 2k-vertices from all Cn. Then, (n-4)-vertices are not dominated from each Cn. Thus, the k-distinct path Pn-4 is obtained by these minor vertices. As a result, |D1|=k(n-4)/2+1+2 is obtained.
Case  2.2. Let D2 be 2-dominating set, and let {u1,u2}∉D2. Clearly, the set D2 includes (n-2)/2+1-vertices of V(Cn)-{u1,u2} of each Cn by Theorem 7. Thus, |D2|=k(n-2)/2+1 is obtained.
By Cases  2.1 and 2.2|D1|=|D2| for k=2 and n≥5. Then we have |D1|<|D2| for k≥3 and n≥5. Furthermore, 2-dominating set is unique for k≥3 and n≥5. As a result, γ2(B(n,k))=k(n-4)/2+1+2 is obtained.
By Cases  1 and 2, the proof is completed.Theorem 39.
LetB(n,k) be an n-gon book, where n≥3 and k≥3; then(21)γ2avBn,k=kn+12-1+1,ifniseven;kn-42+1+3-kn-4/2+1+2kn-2+2,ifnisodd.Proof.
Letu1 and u2 be two major vertices. We have two cases depending on n.
Case  1. Let n be even. We have that the 2-dominating set including the vertex u1 is 2-dominating set of any Cn. Since the vertex u1 is common vertex of each Cn and by Theorem 8, we get γ2u1(B(n,k))=k(n+1)/2-1+1. Similarly, we get γ2u2(B(n,k))=k(n+1)/2-1+1. Let vi1 be minor vertex which is neighbor to the vertex u1 of any Cn, and let vi(n-2) be minor vertex which is neighbor to the vertex u2 in the same graph Cn. It is easy to see that the 2-dominating set including the vertex vi1 is the 2-dominating set including the vertex u2 by Theorem 8. Similarly, the 2-dominating set including the vertex vi(n-2) is the 2-dominating set including the vertex u1. Thus, γ2vi1(B(n,k))=γ2vi(n-2)(B(n,k))=k(n+1)/2-1+1 is obtained. Furthermore, we get γ2vij(B(n,k))=k(n+1)/2-1+1 for every vij∈V(B(n,k))-{u1,u2}, where i∈{1,…,k} and j∈{1,…,n-2}. As a result, γ2av(B(n,k))=k(n+1)/2-1+1 is obtained.
Case  2. Let n be odd. We have two subcases depending on k.
Case  2.1. Let k=2. We know that 2-dominating set is formed by two ways in Case  2 of Theorem 38. Clearly, γ2v(B(n,k))=k(n-4)/2+1+2 is obtained for every vertex v∈V(B(n,k)). As a result, γ2av(B(n,k))=k(n-4)/2+1+2 is obtained.
Case  2.2. Let k≥3. We know that 2-dominating set is unique by Case  2 of Theorem 38. So, γ2av(B(n,k))=k(n-4)/2+1+3-k(n-4)/2+1+2/k(n-2)+2 is obtained by Theorem 10.
By Cases  1 and 2 the proof is completed.Theorem 40.
LetB(n,k) be an n-gon book, where n≥3 and k=2; then(22)γ2avBn,k=kn+12-1+1,ifniseven;kn-42+1+2,ifnisodd.Proof.
The proof directly comes from Theorem39.


## 4. Conclusion

In this study, a new defined graph theoretical parameter, namely, the average lower 2-domination number and the average lower domination number, has been studied for the network vulnerability. Additionally, the stability of popular interconnection networks including cycles has been studied and their domination numbers, 2-domination numbers, average lower domination numbers, and average lower domination 2-numbers, have been computed. These networks have been modeled with the fans, thek-pyramids, and the n-gon books.



---

*Source: 4705493-2016-06-13.xml*