Average covering number for some graphs

Doğan Durgun, D.; Bagatarhan, Ali

doi:10.1051/ro/2018044

Doğan Durgun, D.¹ ; Bagatarhan, Ali ¹

RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 261-268.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

Résumé

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 $\bar{β} (G)$ , where $G$ is simple, connected and undirected graph of order $n \geq 2$ . In a graph $G = (V (G) E (G))$ a subset $S_{v} \subseteq 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

\bar{β} (G) = \frac{1}{| V (G) |} \sum_{v \in 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.

MR Zbl

DOI : 10.1051/ro/2018044

Classification : 68R10, 05C76, 05C70
Mots-clés : Graph theory, graph operations, covering

Affiliations des auteurs :

Doğan Durgun, D. ¹ ; Bagatarhan, Ali ¹

@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2018044/

Bibliographie
Cité par

[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 :