# The Average Lower Connectivity of Graphs

Authors: Ersin Aslan
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

For a vertexv of a graph G, the lower connectivity, denoted by sv(G), is the smallest number of vertices that contains v and those vertices whose deletion from G produces a disconnected or a trivial graph. The average lower connectivity denoted by κav(G) is the value (∑v∈VGsvG)/VG. It is shown that this parameter can be used to measure the vulnerability of networks.  This paper contains results on  bounds for the average lower connectivity and obtains the average lower connectivity of some graphs.


---

## Body

## 1. Introduction

In a communication network, the vulnerability parameters measure the resistance of the network to disruption of operation after the failure of certain stations or communication links. The best known and most useful measures of how well a graph is connected is the connectivity, defined to be the minimum number of vertices in a set whose deletion results in a disconnected or trivial graph. As the connectivity is the worst-case measure, it does not always reflect what happens throughout the graph. Recent interest in the vulnerability and reliability of networks (communication, computer, and transportation) has given rise to a host of other measures, some of which are more global in nature; see, for example, [1, 2].LetG be a finite simple graph with vertex set V(G) and edge set E(G). In the graph G, n denotes the number of vertices. The minimum degree of a graph G is denoted by δ(G). A subset S⊂V(G) of vertices is a dominating set if every vertex in V(G)-S is adjacent to at least one vertex of S. The domination number γ(G) is the minimum cardinality of a dominating set. A subset S of V(G) is called an independent set of G if no two vertices of S are adjacent to G. An independent set S is maximum if G has no independent set S′ with |S′|>|S|. The independence number of G, α(G), is the number of vertices in a maximum independent set of G.Henning [3] introduced the concept of average independence and average domination. For a vertex v of a graph G, the lower independence number, denoted by iv(G), is the minimum cardinality of a maximal independent set of G that contains v, and the lower domination number, denoted by γv(G), is the minimum cardinality of a dominating set of G that contains v. The average lower independence number of G, denoted by iav(G), is the value (∑v∈V(G)iv(G))/|V(G)| and the average lower domination number of G, denoted by γav(G), is the value (∑v∈V(G)γv(G))/|V(G)|. Since γv(G)≤iv(G) holds for every vertex v, we have γav(G)≤iav(G) for any graph G. Also, it is clear that i(G)=min⁡{iv(G)∣v∈V(G)} and γ(G)=min⁡{γv(G)∣v∈V(G)} so γ(G)≤γav(G) and i(G)≤iav(G).The (u,v)-connectivity of G, denoted by κG(u,v), is defined to be the maximum value of k for which u and v are k-connected. It is a well-known fact that the connectivity κ(G) equals min⁡{κG(u,v)u,v∈V(G)}.In 2002, Beineke et al. [4] introduced a parameter to give a more refined measure of the global “amount” of connectivity. If the order of G is n, then the average connectivity of G, denoted by κ-(G), is defined to be κ-(G)=(∑u,vκG(u,v))/(n2). The expression ∑u,vκG(u,v) is sometimes referred to as the total connectivity of G. Clearly, for any graph G, κ-(G)≥κ(G).There are a lot of researches on the connectivity of a graph [5]. Many works provide sufficient conditions for a graph to be maximally connected [6–8]. The average connectivity has been extensively studied [4, 9].


## 2. The Average Lower Connectivity of a Graph

We introduce a new vulnerability parameter, the average lower connectivity. For a vertexv of a graph G, the lower connectivity, denoted by sv(G), is the smallest number of vertices that contains v and those vertices whose deletion from G produces a disconnected or a trivial graph. We observe that(i)
1≤sv(G)≤n-1;(ii)
sv(G)=1 if and only if v is a cut vertex;(iii)
sv(G)=n-1 if and only if G-v is complete.The average lower connectivity denoted by κav(G) is the value (∑v∈V(G)sv(G))/n, where n will denote the number of vertices in graph G and ∑v∈V(G)sv(G) will denote the sum over all vertices of G. For any graph G, κ(G)=min⁡{sv(G)∣v∈V(G)} so κav(G)≥κ(G). We also observe that(i)
κav(G)≤n-1;(ii)
κav(G)=n-1 if and only if G is complete.Example 1.
Let the graphG be 3-cycle with one additional vertex and edge, as shown in Figure 1. It is easy to see that sa(G)=2, sb(G)=2, sc(G)=1, and sd(G)=3 and we have κav(G)=(2+2+1+3)/4=2.
LetG1 and G2 be graphs. Now one can ask the following question: is the average lower connectivity a suitable parameter? In other words, does the average lower connectivity distinguish between G1 and G2?Figure 1
3-cycleG: with one additional vertex and edge.For example, consider the graphs in Figure2.The graphsG1 and G2.
(a)
(b)It can be easily seen that the connectivity and average connectivity of these graphs are equal:(1)κ(G1)=κ(G2)=κ-(G1)=κ-(G2)=1.
On the other hand, the average lower connectivity of G1 and G2 is different:
(2)κav(G1)=1,8,κav(G2)=1,6.
Thus, the average lower connectivity is a better parameter than the connectivity and average connectivity to distinguish these two graphs. The average parameters have been found to be more useful in some circumstances than the corresponding measures based on worst-case situations.Theorem 2.
LetG be a connected graph. Then,
(3)κav(G)<κ(G)+2.Proof.
For every vertex ofG, sv(G)≤κ(G)+2. For at least one vertex v, sv(G)=κ(G). Hence, the inequality is strict. Then,
(4)κav(G)<κ(G)+2.
The proof is completed.Theorem 3.
LetG be a connected graph. Then,
(5)κav(G)≤κav(G+e).Proof.
It is easy to see thatsv(G)≤sv(G+e). Therefore,
(6)∑v∈V(G)sv(G)n≤∑v∈V(G)sv(G+e)n.
So, we have
(7)κav(G)≤κav(G+e).
The proof is completed.Theorem 4.
LetG be a k-connected and k-regular graph. Then,
(8)κav(G)=k.Proof.
The cardinality ofsv(G)-sets is always the same for every vertex of any graph G and equals k. Then, we have
(9)κav(G)=∑v∈V(G)sv(G)n=n·kn=k.
This means that the proof is completed.It is obvious that we can give the following equality for the average lower connectivity of the cycleCn.(i)
The average lower connectivity of the cycleCn is 2.Theorem 5.
LetG be a connected graph. Then,
(10)κav(G)≤δ(G)+2.Proof.
For every vertex ofG, sv(G)≤δ(G)+2. Thus,
(11)κav(G)=∑v∈V(G)sv(G)n≤n·(δ(G)+2)n,κav(G)≤δ(G)+2.
The proof is completed.


## 3. Average Lower Connectivity of Several Specific Graphs

In this section, we determine the average lower connectivity of several special graphs.Theorem 6.
LetT be a tree with order n. If T has k vertices with degree 1, then
(12)κav(T)=n+kn.Proof.
Assume thatT has k vertices with degree 1 and n-k vertices with degree at least 2. Let vertices set of T be V(T)=V(G1)∪V(G2) where in V(G1) the set contains k vertices with degree 1; in V(G2) the set contains n-k vertices with degree at least 2. If v∈V(G1), then sv(G1)=2. We have to repeat this process for k vertices with degree 1. If v∈V(G2), then sv(G2)=1. We have to repeat this process for n-k vertices with degree at least 2. Thus, we have
(13)κav(T)=∑v∈V(T)sv(T)|V(T)|=k·2+(n-k)·1n=n+kn.
The proof is completed.Corollary 7.
The average lower connectivity of(a)
the pathPn is (n+2)/n;(b)
the starK1,n-1 is (2n-1)/n;(c)
the cometCt,r is (2r+t+1)/(t+r).Theorem 8.
LetKr,s be a complete bipartite graph. Then
(14)κav(Kr,s)={s2+sr+rr+s,ifs<r;r,ifr=s.Proof.
Let the partite sets ofKr,s be R and S with |R|=r and |S|=s. We distinguish two cases.
Case  1. If r=s, then by Theorem 4 we have κav(Kr,s)=r.
Case  2  (r<s). For x∈R, a minimum disconnecting set of G that contains x must be S∪{x}, so sx(G)=s+1. On the other hand, for y∈S, a minimum disconnecting set of G that contains y must be R, so sy(G)=r. Elementary computation yields the result.Definition 9.
The wheel graph withn-1 spokes, Wn, is the graph that consists of an (n-1)-cycle and one additional vertex, say u, that is adjacent to all the vertices of the cycle. In Figure 3, we display W7.Figure 3
The wheel graphW7.Theorem 10.
LetWn be a wheel graph. Then,
(15)κav(Wn)=3.Proof.
The wheel graphWn has n vertices. The cardinality of sv(G)-sets is always the same for every vertex of any Wn and equals 3. Then, we have
(16)κav(Wn)=∑v∈V(Wn)sv(Wn)n=n·3n=3.
This means that the proof is completed.Definition 11.
The gear graph is a wheel graph with a vertex added between each pair adjacent to graph vertices of the outer cycle. The gear graphGr has 2r+1 vertices and 3r edges. In Figure 4 we display G6.Figure 4
The gear graphG6Theorem 12.
LetGr be a gear graph. Then,
(17)κav(Gr)=5r+32r+1.Proof.
Let vertices set ofGr be V(Gr)=(H1)∪V(H2)∪V(H3) where in V(H1) the set contains 1 vertex with degree n, V(H2) the set contains n vertices with degree 2, and V(H3) the set contains n vertices with degree 3.If v∉V(H3), then sv(G)=3. If v∈V(H3), then sv(G3)=2. Therefore,
(18)κav(Gr)=∑v∈V(Gr)sv(Gr)2r+1=(r+1)·3+2·r2r+1=5r+32r+1.
The proof is completed.Now we give the definition of Cartesian product.Definition 13.
The Cartesian productG1×G2 of graphs G1 and G2 has V(G1)×V(G2) as its vertex set and (u1,u2) is adjacent to (v1,v2) if either u1=v1 and u2 is adjacent to v2 or u2=v2 and u1 is adjacent to v1.
Connectivity of graph products has already been studied by different authors. In [10] it is proved that κ(G1×G2)≥κ(G1)+κ(G2).Theorem 14.
LetG1 and G2 be two connected graphs; then
(19)κav(G1×G2)≥κ(G1×G2).Proof.
We knowκav(G)≥κ(G). Therefore, we get
(20)κav(G1×G2)≥κ(G1×G2).
The proof is completed.Proposition 15.
For positive integerm≥3,(i)
κav(K2×Pm)=2;(ii)
κav(K2×Cm)=3.Proposition 16.
Letr≥3 and t≥3 be positive integers. Then
(21)(i)κav(Pr×Pt)={239,ifr=3,t=3;3-2t,ifr=3,t≥4;3-8r·t,ifr≥4,t≥4.(ii)κav(Pr×Ct)={3,ifr=3,4,t≥3;4-4r,ifr≥5,t≥4.(iii)κav(Cr×Ct)=4.



---

*Source: 807834-2014-02-12.xml*