The average lower reinforcement number of a graph

Turaci, Tufan; Aslan, Ersin

doi:10.1051/ita/2016015

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 = (V (G), E (G))$ 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. $𝑙𝑜𝑤𝑒𝑟 𝑟𝑒𝑖𝑛𝑓𝑜𝑟𝑐𝑒𝑚𝑒𝑛𝑡 𝑛𝑢𝑚𝑏𝑒𝑟$ , denoted by $r_{e^{*}} (G)$ , is the minimum cardinality of $𝑟𝑒𝑖𝑛𝑓𝑜𝑟𝑐𝑒𝑚𝑒𝑛𝑡 𝑠𝑒𝑡$ in $G$ that contains the edge $e^{*}$ of the complement graph $\bar{G}$ . The $𝑎𝑣𝑒𝑟𝑎𝑔𝑒 𝑙𝑜𝑤𝑒𝑟 𝑟𝑒𝑖𝑛𝑓𝑜𝑟𝑐𝑒𝑚𝑒𝑛𝑡 𝑛𝑢𝑚𝑏𝑒𝑟$ of $G$ is defined by $r_{a v} (G) = \frac{1}{| E (\bar{G}) |} Σ_{e^{*} \in E (\bar{G})} r_{e^{*}} (G)$ . 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.

MR Zbl

DOI : 10.1051/ita/2016015

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

Affiliations des auteurs :

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.

@article{ITA_2016__50_2_135_0,
     author = {Turaci, Tufan and Aslan, Ersin},
     title = {The average lower reinforcement number of a graph},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {135--144},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {2},
     year = {2016},
     doi = {10.1051/ita/2016015},
     mrnumber = {3580107},
     zbl = {1352.05101},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2016015/}
}

TY  - JOUR
AU  - Turaci, Tufan
AU  - Aslan, Ersin
TI  - The average lower reinforcement number of a graph
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 135
EP  - 144
VL  - 50
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2016015/
DO  - 10.1051/ita/2016015
LA  - en
ID  - ITA_2016__50_2_135_0
ER  -

%0 Journal Article
%A Turaci, Tufan
%A Aslan, Ersin
%T The average lower reinforcement number of a graph
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 135-144
%V 50
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2016015/
%R 10.1051/ita/2016015
%G en
%F ITA_2016__50_2_135_0

Turaci, Tufan; Aslan, Ersin. The average lower reinforcement number of a graph. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 2, pp. 135-144. doi : 10.1051/ita/2016015. http://www.numdam.org/articles/10.1051/ita/2016015/

Bibliographie
Cité par

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

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. | DOI | MR | Zbl

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

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 | DOI | MR | Zbl

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

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

X. Chen, L. Sun and D. Ma, Bondage and reinforcement number of $γ_{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. | DOI | MR | Zbl

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

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. | DOI | MR

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. | DOI | MR | Zbl

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

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

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

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. | DOI | MR | Zbl

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

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

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. | DOI | MR

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

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

Cité par Sources :