# The Average Covering Number of a Graph

Authors: Derya Dogan; Pinar Dundar
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

There are occasions when an average value of a graph parameter gives more
useful information than the basic global value. In this paper, we introduce the concept of the average covering number of a graph (the covering number of a graph is the minimum number of vertices in a set with the property that every edge has a vertex in the set). We establish relationships between the average covering number and some other graph parameters, find the extreme values of the average covering number among all graphs of a given order, and find the average covering number for some families of graphs.


---

## Body

## 1. Introduction

The stability and reliability of a network are of prime importance to 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. As the network begins losing connection lines or centers, eventually, there is a loss of effectiveness. If the communication network is modelled as a simple, undirected, connected, and unweighted graphG deterministic measures tend to provide the worst-case analysis of some aspects of the overall disconnection process [1, 2].Theconnectivity of a graph G is the minimum number of vertices whose removal from G results in a disconnected or trivial graph and is denoted by κ(G). This parameter has been extensively studied. Recent interest in the vulnerability and reliability of networks has given rise to a host of other measures, some of which are more global in nature. Beineke et al. introduced a parameter to give a more refined measure of the global “amount” of connectivity in 2002 [3–5]. The average connectivityof a graph G with n vertices, denoted by κ¯(G), is defined as  ∑u,v∈V(G)‍(κ(u,v)/(n2)), where κ(u,v) is the minimum number of vertices whose deletion makes v unreachable from u. By Menger’s theorem, κ(u,v) is equal to maximum number of internally disjoint paths joining u and v [6]. Note that the relationship between connectivity and average connectivity is κ¯(G)≥κ(G)=minu,v∈V(G)κ(u,v) [3]. Average connectivity is much more attractive for applications because it can be computed in polynomial time whereas other global parameters, such as toughness and integrity, are NP-hard computationally. There are more global parameters to investigate vulnerability. The other example of global parameters is average domination number introduced by Henning in 2004 [7]. For another example of global parameters see [8, 9].Other average parameters have been found to be more useful in some circumstances than the corresponding measures based on worst-case situations. For example, the average distance between vertices in a graph was introduced as a tool in architecture and later turned out to be more valuable than the diameter when analyzing transportation networks (for excellent survey of this topic, see [10]).Throughout this paper, unless otherwise specified, a graphG is denoted by G=(V(G),E(G)), where V(G) and E(G) are vertex and edge sets of G, respectively. In the graph G, n and m denote the number of vertices and the number of edges, respectively. G is a simple, connected, and undirected graph of order n≥2 and also we use the terminology of [6].In a graphG=(V(G),E(G)), a set S of vertices is called a vertex coverif each edge of G is incident with at least one vertex in S. The covering numberα(G) is the minimum cardinality of a cover of G [11]. A cover of this cardinality is called a minimum cover. In this paper, we define average covering number of a graph. Before we define the average covering number, we need a local version. Given a vertex v in graph G, we define the local covering number    αv(G) to be the minimum order of a cover that contains v. Note that obviously αv(G)=α(G) or α(G)+1. The average covering numberα¯(G) of a graph G is (1/|V(G)|)∑v∈V(G)‍αv(G), where n is order of G and the sum is over all n vertices. That is, the average covering number of a graph is simply the mean of the local covering numbers.For example, the graphG in Figure 1 has α(G)=3, with one minimum cover being {a,b,d}. It can easily be checked that graphs G and H have not only equal covering numbers but also equal independence numbers, domination numbers, and connectivity, so how can we distinguish between the graphs? In fact, every vertex except f is in a minimum cover, and so it follows that α¯(G)=(3+3+3+3+3+4)/6=3.16. The reader can check that α¯(H)=3.5.Figure 1We can say graphH is more reliable than graph G since α¯(G)<α¯(H). If we consider the graphs G-{a} and H-{c}, then we can see that each graph has one isolated vertex and G-{a} contains P4 but H-{c} contains a cycle in it. This means H-{c} is more reliable than G-{a}.


## 2. Main Results of the Average Covering Number of a Graph

Below we present two main theorems and give lower and upper bounds of average covering number of a graph.Theorem 1.
IfG is a graph with at least one edge, then
(1)α(G)≤α¯(G)<α(G)+1.Proof.
Thatα(G)≤α¯(G)≤α(G)+1 follows at once from the observation about possible values of the local covering number made earlier. It is also easy to see that a minimum cover never includes all of the vertices of a graph, and if a graph has an edge, then every cover has at least one vertex. Hence, for at least one vertex v, αv(G)=α(G). Hence, the second inequality is strict. Then,
(2)α(G)≤α¯(G)<α(G)+1.Theorem 2.
IfG is a graph with at least one edge, then
(3)αv(G)=α(G-v)+1.Proof.
Clearly, ifS is a cover of G-v, then S∪{v} is a cover of G, so the inequality
(4)αv(G)≤α(G-v)+1
holds. On the other hand, if Sv is a minimum cover of G-v, then clearly S is a cover of G, so the reverse inequality also holds. Therefore, αv(G)=α(G-v)+1.Corollary 3.
LetG be a graph and v∈V(G). Then
(5)α¯(G)=1+∑‍α(G-v)n.Proof.
LetG be a graph and v∈V(G). By Theorem 2,  αv(G)=α(G-v)+1, so,
(6)α¯(G)=∑v∈V(G)αv(G)n=∑v∈V(G)(1+α(G-v))n=1+∑v∈V(G)α(G-v)n.Theorem 4.
IfH is any subgraph of G, then α-(H)≤α-(G).Proof.
LetH be any subgraph of G. If S is a cover of G, then S∩V(H) obviously covers H. Therefore, α¯(H)≤α¯(G).Corollary 5.
The covering number of every connected graph other than a star is at least 2, and that of every connected graph of ordern other than a complete graph is at most n-2, 2≤α¯(G)≤n-2+2/n.Theorem 6.
If the independence number ofG is β, then the average covering number is at most n-β+β/n.Proof.
It is easy to see this from Gallai’s theorem [6].Theorem 7.
IfG is vertex transitive, then α¯(G)=α(G).Proof.
Let a graphG be vertex transitive, then for every two vertices u and v of G, there exists an automorphism ϕ of G such that ϕu=v. It is easy to see from this property that α¯(G)=α(G).Theorem 8.
LetG be a connected graph and n≥3. Then,
(7)2-1n≤α¯(G)≤n-1.Proof.
It is easy to see that for the starK{1,n-1} with n≥3, the local covering number for one vertex is 1, while for all others it is 2. Hence, α¯(G)≥((n-1)·2+1)/n=(2n-1)/n=2-1/n. On the other hand, if a connected graph is not a star, then every cover has at least two vertices. This proves the lower bound. Obviously, every set of n vertices in the complete graph Kn is a minimum cover, and since every vertex is in such a set, the greatest average covering number of a graph of order n is n-1. Therefore,
(8)2-1n≤α¯(G)≤n-1.Theorem 9.
IfG is a graph order n and if v has degree n-1, then α¯(G-v)<α¯(G).Proof.
LetG be a graph of order n and v has degree n-1, G-v means delete the vertex v from the graph G. It is easy to see that α¯(G-v)<α¯(G).Theorem 10.
LetG1 and G2 be two graphs of the same order and β(G1)<β(G2). Then,
(9)α¯(G1)>α¯(G2).Proof.
LetG1 and G2 be two graphs with the same order and β(G1)<β(G2), then α(G1)>α(G2) by Gallai’s theorem. By Theorem 2, we know αv(G)=α(G-v)+1 then we can say αv(G1)>αv(G2). By definition of average covering number of  a graph
(10)α¯(G1)>α¯(G2).Now we give average covering number of some classes of graphs. The following results follow directly from the definition ofα¯(G).Proposition 11.
(i) IfKn is a complete graph of order n, then α¯(Kn)=n-1.
(ii) IfPn is a path, then α¯(P{2k})=k and α¯(P{2k+1})=k+(k+1)/(2k+1).
This relies on the observations that ifPn=v1,v2,…,vn, then the set of even-numbered vertices and the set of odd-numbered vertices form covers Pn and  that since the maximum degree of a vertex is 2, the covering number is at least ⌈(n-1)/2⌉.
(iii) IfCn is a cycle of order n, then α¯(Cn)=⌈n/2⌉.
(iv) IfKm,n is a complete bipartite graph, then
(11)α¯(Km,n)={m,m=n,m+n(m+n),m<n.


## 3. Algorithm for Average Covering Number

In this section we introduce an algorithm to find the average covering number of any graph.In this algorithm we use some variables which we defined below:n is the number of vertices of the graph,is the set which gives the covering number,S is the sum of αv for each vertex,α
¯ is the average covering number of the graph.Step  0. Start.Step  1. Find covering number of a graph.Step  2. If v∈V(G) is the element of α-set, then αv=α; otherwise αv=α+1.Step  3. Take the sum of each αv; say S.Step  4.     α¯=S/n.Step  5. Stop.We can use any known algorithm to find covering number. In the literature there are lots of algorithms; to find covering number for the first step of algorithm we can use any of them (for one example of this, see [12]).


## 4. Conclusion

Any communication network can be modelled as a connected graph. In this paper, we introduce the new parameter for reliability of a graph, the average covering number. If we want to choose the more stable graph among the graphs which have the same order and the same size, one way is to choose the graph whose average covering number is greater than those of the others. By Theorem2, we can use existing algorithms for the covering number α(G) to find the average covering number α¯(G).



---

*Source: 849817-2013-09-19.xml*