The average lower reinforcement number of a graph

Turaci, Tufan; Aslan, Ersin

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

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.

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

E. Aslan, The Average Lower Connectivity of Graphs. J. Appl. Math. 2014 (2014) 807834. | MR | Zbl | DOI

E. Aslan and A. Kırlangıç, The Average Lower Domination Number of Graphs. Bull. Int. Math. Virtual Inst. 3 (2013) 155–160. | MR | Zbl

A. Aytaçand T. Turacı, Vertex Vulnerability Parameter of Gear Graphs. Int. J. Found. Comput. Sci. 22 (2011) 1187–1195. | MR | Zbl | DOI

A. Aytaç, T. Turacı and Z.N. Odabaş, On The Bondage Number of Middle Graphs. Math. Notes 93 (2013) 803–811. | MR | Zbl | DOI

A. Aytaç, Z.N. Odabas and T. Turacı, The Bondage Number for Some Graphs. C. R. Acad. Bulg. Sci. 64 (2011) 925–930. | MR | Zbl

V. Aytaç, Average Lower Domination Number in Graphs. C. R. Acad. Bulg. Sci. 65 (2012) 1665–1674. | MR | Zbl

C.A. Barefoot, R. Entringer and H. Swart, Vulnerability in graphs-a comparative survey. J. Comb. Math. Comb. Comput. 1 (1987) 13–22. | MR | Zbl

J.R.S. Blair, W. Goddard, S.T. Hedetniemi, S. Horton, P. Jones and G. Kubicki, On domination and reinforcement numbers in trees. Discrete Math. 308 (2008) 1165–1175 | MR | Zbl | DOI

L.W. Beineke, O.R. Oellermann and R.E. Pippert, The Average Connectivity of a Graph. Discrete Math. 252 (2002) 31–45. | MR | Zbl | DOI

M. Blidia, M. Chellali and F. Maffray, On Average Lower Independence and Domination Number in Graphs. Discrete Math. 295 (2005) 1–11. | MR | Zbl | DOI

X. Chen, L. Sun and D. Ma, Bondage and reinforcement number of $\gamma {}_f$ for complete multipartite graph. J. Beijin Inst. Technol. 12 (2003) 89–91. | MR | Zbl

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

G.S. Domke and R.C. Laskar, The bondage and reinforcement numbers of $\gamma {}_f$ for some graphs. Discrete Math. 167-168 (1997) 249–259. | MR | Zbl | DOI

P. Dündar, T. Turacı and D. Dog˜an, Weak and Strong Reinforcement Number of a Graph. Int. J. Math. Comb. 3 (2010) 91–97. | Zbl

H. Frank and I.T. Frisch, Analysis and design of survivable Networks. IEEE Trans. Commun. Technol. 18 (1970) 501–519. | MR | DOI

J. Ghoshal, R. Laskar, D. Pillone and C. Wallis, Strong bondage and strong reinforcement numbers of graphs. Congr. Numer. (English) 108 (1995) 33–42. | MR | Zbl

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs. Advanced Topic. Marcel Dekker, Inc, New York (1998). | MR | Zbl

M.A. Henning, Trees with Equal Average Domination and Independent Domination Numbers. Ars Comb. 71 (2004) 305–318. | MR | Zbl

M.A. Henning and O.R. Oellermann, The Average Connectivity of a Digraph. Discrete Appl. Math. 140 (2004) 143–153. | MR | Zbl | DOI

M.A. Henning, N.J. Rad and J. Raczek, A note on total reinforcement in graph. Discrete Appl. Math. 159 (2011) 1443–1446. | MR | Zbl | DOI

F.T. Hu and J.M. Xu, On the complexity of the bondage and reinforcement problems. J. Complexity 28 (2012) 192–201 | MR | Zbl | DOI

J. Huang, J.W. Wang and J.M. Xu, Reinforcement number of digraphs. Discrete Appl. Math. 157 (2009) 1938–1946. | MR | Zbl | DOI

J. Kok and C.M. Mynhardt, Reinforcement in Graphs. Congr. Numer. 79 (1990) 225–231. | MR | Zbl

N. Li, X. Hou, J. Chen and J.M. Xu, Signed reinforcement numbers of certain graphs. AKCE Int. J. Graphs Comb. 9 (2012) 59–70. | MR | Zbl

Y. Lu, F.T. Hu and J.M. Xu, On the p-reinforcement and the complexity. J. Combin,. Optim. 29 (2015) 389–405. | MR | Zbl | DOI

I. Mishkovski, M. Biey and L. Kocarev, Vulnerability of complex Networks. Commun. Nonlin. Sci. Numer Simul. 16 (2011) 341–349. | MR | Zbl | DOI

K.T. Newport and P.K. Varshney, Design of survivable communication networks under performance constraints. IEEE Trans. Reliab. 40 (1991) 433–440. | Zbl | DOI

N.J. Rad and S.M. Sheikholeslami, Roman reinforcement in graphs. Bull. Inst. Comb. Appl. 61 (2011) 81–90. | MR | Zbl

N. Sridharan, M.D. Elias and V.S.A. Subramanian, Total reinforcement number of a graph. AKCE Int. J. Graphs Comb. 4 (2007) 197–202. | MR | Zbl

G.H. Tuncel, T. Turaci and B. Coskun, The Average Lower Domination Number and Some Results of Complementary Prisms and Graph Join. J. Adv. Res. Appl. Math. 7 (2015) 52–61. | MR | DOI

T. Turaci, On the average lower bondage number a graph. To appear in RAIRO-Oper. Res. (2016). | DOI | MR | Numdam

T. Turaci and M. Okten, Vulnerability of Mycielski Graphs via Residual Closeness. Ars Comb. 118 (2015) 419–427. | MR | Zbl

J.H. Zhang, H.L. Liu and L. Sun, Independence bondage and reinforcement number of some graphs. Trans. Beijin Inst. Technol. 23 (2003) 140–142. | MR | Zbl