Average weakly edge domination number in graphs

Year 2018, Volume: 3 Issue: 1, 51 - 62, 30.04.2018

Mehmet Ali Balci Pinar Dundar

Abstract

Communication is supposed to be continuous in a network design. It is important for a network to be tough so that  communication is not interrupted in case any damage. In this paper, it is investigated how to decide which graph model to choose,  when a selection is needed to make between different graphs to be used for a network model when all known vulnerability measures are same. We introduce the concept of the average weakly edge domination number of a graph as a new vulnerability measure. We establish relationships between the average weakly edge domination number and some other graph parameters, and the extreme values of given measure among all graphs and average weakly edge domination number for some families of graphs. Also a polynomial time  algorithm with complexity O(n3) is given.

Keywords

Average weakly edge domination, edge distance

References

• [1] A Aytac¸, The common-neighbourhood of a graph, Boletim da Sociedade Paranaense de Matematica, 35(1) 23–32 (2017).
• [2] A. Brandst¨adt, Van B. Le, Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics (1999).
• [3] A. H. Esfahanian, S. L. Hakimi, On computing a conditional edge-connectivity of a graph. Information Processing Letters, 27(4), pp.195-199., (1988).
• [4] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, G. Monfardini, Computational capabilities of graph neural networks, IEEE Transactions on Neural Networks, 20(1), pp.81–102, (2009).
• [5] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, North-Holland, New York (1976).
• [6] K. Kanwar, H. Kumar, S. Kaushal, AMetric to Compare Vulnerability of the Graphs of Different Sizes, Electronic Notes in Discrete Mathematics, 63, pp.525–533, (2007).
• [7] K. S. Bagga, L. W. Beineke, R. E. Pippert, M. J. Lipman, A classification scheme for vulnerability and reliability parameters of graphs, Mathematical and Computer Modelling, 17(11), pp.13–16, (1993).
• [8] M. A. Balcı, P. D¨undar, Average Edge-Distance in Graphs, Selcuk J. Appl. Math., N.11, pp.63–70 (2010).
• [9] M. A. Balcı, ¨O. Akg¨uller, Average Weakly Hyperedge Domination Number for a Hypergraph and Actor-Network Application, International Journal of Modeling and Optimization, 4(5), p.346, (2014).
• [10] M. A. Balcı, S. P. Atmaca, ¨O. Akg¨uller, Hyperpath Centers, In Advanced Computational Methods for Knowledge Engineering, pp. 129–137, (2016).
• [11] M. A. Balcı, ¨O. Akg¨uller, Soft Vibrational Force on Stock Market Networks, Library Journal, 3, p.e3050 (2016).
• [12] M. A. Balcı, S. P. Atmaca, ¨O. Akg¨uller, Graph Theoretical Approach To Detection of Outliers in Point Clouds, International Journal of Advances in Science Engineering and Technology, 3(4), pp.59–61 (2015).
• [13] P. D¨undar, A. Aytac¸, Integrity of total graphs via certain parameters, Mathematical Notes 76(5-6) 665–672 (2004).
• [14] R. Diestel, Graph Theory, Springer Verlag Heidelberg, New York (2005).
• [15] S. K. Vaidya, N. J. Kothari, Domination Integrity of Splitting and Degree Splitting Graphs of Some Graphs. Advances and Applications in Discrete Mathematics 17(2) 185 (2016).
• [16] S. M. Wagner, N. Neshat, Assessing the vulnerability of supply chains using graph theory, International Journal of Production Economics, 126(1), pp.121–129 (2010).
• [17] T. Davidovi´c, T. G. Crainic, Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems. Computers & operations research, 33(8), pp.2155–2177 (2006).
• [18] W.Mader, Connectivity and Edge-Connectivity in Finite Graphs, Surveys in Combinatorics, London Mathematical Society Lecture Notes Series, 38, pp. 66–95 (1979).