The average lower reinforcement number of a graph

Turaci, Tufan¹ ; Aslan, Ersin²

¹ Department of Mathematics, Faculty of Science, Karabük University, 78050, Karabük, Turkey.
² Turgutlu Vocational Training School, Celal Bayar University, 45400 Manisa, Turkey.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 2, pp. 135-144

Résumé

Let $G=\left(V\right(G),E(G\left)\right)$ be a simple undirected graph. The reinforcement number of a graph is a vulnerability parameter of a graph. We have investigated a refinement that involves the average lower reinforcement number of this parameter. $\mathrm{𝑙𝑜𝑤𝑒𝑟}\mathrm{𝑟𝑒𝑖𝑛𝑓𝑜𝑟𝑐𝑒𝑚𝑒𝑛𝑡}\mathrm{𝑛𝑢𝑚𝑏𝑒𝑟}$, denoted by $r_{e^{*}}\left(G\right)$, is the minimum cardinality of $\mathrm{𝑟𝑒𝑖𝑛𝑓𝑜𝑟𝑐𝑒𝑚𝑒𝑛𝑡}\mathrm{𝑠𝑒𝑡}$ in $G$ that contains the edge $e^{*}$ of the complement graph $\overline{G}$. The $\mathrm{𝑎𝑣𝑒𝑟𝑎𝑔𝑒}\mathrm{𝑙𝑜𝑤𝑒𝑟}\mathrm{𝑟𝑒𝑖𝑛𝑓𝑜𝑟𝑐𝑒𝑚𝑒𝑛𝑡}\mathrm{𝑛𝑢𝑚𝑏𝑒𝑟}$ of $G$ is defined by $r_{av}\left(G\right)=\frac{1}{\left|E\right(\overline{G}\left)\right|}{\Sigma }_{e^{*}\in E\left(\overline{G}\right)}{r}_{e^{*}}\left(G\right)$. In this paper, we define the average lower reinforcement number of a graph and we present the exact values for some well−known graph families.

Détail

DOI : 10.1051/ita/2016015

Classification : 05C40, 05C69, 68M10, 68R10
Keywords: Graph vulnerability, connectivity, network design and communication, domination number, reinforcement number, average lower reinforcement number