Average covering number for some graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 261-268.

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 β ¯ ( G ) , where G is simple, connected and undirected graph of order n 2 . In a graph G = ( V ( G ) E ( G ) ) a subset S v V ( G ) 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 V ( G ) β v .
In this paper, the average covering numbers of k th power of a cycle C n k and P n P m , C m , cartesian product of , P P n and P m , cartesian product of P n and C m are given, respectively.

DOI : 10.1051/ro/2018044
Classification : 68R10, 05C76, 05C70
Mots-clés : Graph theory, graph operations, covering
Doğan Durgun, D. 1 ; Bagatarhan, Ali 1

1
@article{RO_2019__53_1_261_0,
     author = {Do\u{g}an Durgun, D. and Bagatarhan, Ali},
     title = {Average covering number for some graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {261--268},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1},
     year = {2019},
     doi = {10.1051/ro/2018044},
     zbl = {1442.68166},
     mrnumber = {3912474},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018044/}
}
TY  - JOUR
AU  - Doğan Durgun, D.
AU  - Bagatarhan, Ali
TI  - Average covering number for some graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 261
EP  - 268
VL  - 53
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018044/
DO  - 10.1051/ro/2018044
LA  - en
ID  - RO_2019__53_1_261_0
ER  - 
%0 Journal Article
%A Doğan Durgun, D.
%A Bagatarhan, Ali
%T Average covering number for some graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 261-268
%V 53
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018044/
%R 10.1051/ro/2018044
%G en
%F RO_2019__53_1_261_0
Doğan Durgun, D.; Bagatarhan, Ali. Average covering number for some graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 261-268. doi : 10.1051/ro/2018044. http://www.numdam.org/articles/10.1051/ro/2018044/

[1] L.W. Beineke, O.R. Oellermann and R.E. Pippert, The average connectivity of a graph. Discrete Math. 252 (2002) 31–45. | DOI | MR | Zbl

[2] G. Chartrand, L. Lesniak and P. Zhang, Textbooks in Mathematics, Graphs & Digraphs. 6th edition. A Chapman & Hall Book (2016). | MR

[3] V. Chvatal, Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215–228. | DOI | MR | Zbl

[4] P. Dankelmann and O.R. Oellermann, Bounds on the average connectivity of a graph. Discrete Appl. Math. 129 (2003) 305–318. | DOI | MR | Zbl

[5] D. Dogan and P. Dundar, The average covering number of a graph. J. Appl. Math. 2013 (2013) 849817. | DOI | MR | Zbl

[6] D. Dogan and P. Dundar, The average covering number on graph operations, J. Logic Math. Linguist. Appl. Sci. 1 (2016).

[7] M.A. Henning and O.R. Oellermann, The average connectivity of regular multipartite tournaments. Aust. J. Comb. 23 (2001) 101–113. | MR | Zbl

[8] M.A. Henning, Trees with equal average domination and independent domination numbers. Ars Comb. 71 (2004) 305–318. | MR | Zbl

[9] D. Moazzami, Tenacity of a graph with maximum connectivity. Discrete Appl. Math. 159 (2011) 367–380. | DOI | MR | Zbl

[10] S. Win, On a connection between the existence of k-trees and the toughness of a graph. Graphs Comb. 5 (1989) 201–205. | DOI | MR | Zbl

Cité par Sources :