Average covering number for some graphs

Arts and Science Faculty, Manisa Celal Bayar University, 45140 Manisa, Turkey

^* Corresponding author: derya.dogan@cbu.edu.tr

Received: 3 May 2017
Accepted: 21 May 2018

Abstract

The interconnection networks are modeled by means of graphs to determine the reliability and vulnerability. There are lots of parameters that are used to determine vulnerability. The average covering number is one of them which is denoted by $\overline{\beta }\left(G\right)$, where G is simple, connected and undirected graph of order n ≥ 2. In a graph G = (V(G), E(G)) a subset $S_v\subseteq V\left(G\right)$ of vertices is called a cover set of G with respect to v or a local covering set of vertex v, if each edge of the graph is incident to at least one vertex of S_v. The local covering number with respect to v is the minimum cardinality of among the S_v sets and denoted by β_v. The average covering number of a graph G is defined as β̅(G) = 1/|v(G)| ∑_ν∈v(G)β_ν In this paper, the average covering numbers of kth power of a cycle $C_n^k$ and P_n □ P_m, P_n □ C_m, cartesian product of P_n and P_m, cartesian product of P_n and C_m are given, respectively.