EXPONENTIAL DOMINATION OF TREE RELATED GRAPHS

Year 2019, Volume: 9 Issue: 3, 461 - 472, 01.09.2019

A. Aytaç B. A. Atakul

Abstract

The well-known concept of domination in graphs is a good tool for analyzing situations that can be modeled by networks. Although a vertex in the graph can exert in uence on, or dominate, all vertices in its immediate neighbourhood, in some real world situations, this can be change. The vertex can also in uence all vertices within a given distance. This situation is characterized by distance domination. The in uence of the vertex in the graph doesn't extend beyond its neighbourhood and even this in uence decreases with distance. Up to the present, no framework for this situation has been put forward yet. The dominating power of the vertex in the graph decreases exponentially, with distance by the factor 1=2. Hence a vertex v can be dominated by a neighbour of v or by a number of vertices that are not too far from v. In this paper, we study the vulnerability of interconnection networks to the in uence of individual vertices, using a graph-theoretic concept of exponential domination number as a measure of network robustness.

Keywords

Graph vulnerability, Network design and communication, Domination, Ex- ponential domination number, Trees.

References

• [1] Anderson, M., Brigham, R. C., Carrington, J. R., Vitray, R. P., Yellen, J., (2009). On Exponential Domination of CmxCn, AKCE J.Graphs. Combin.,6, No. 3 341-351.
• [2] Ayta¸c, V. and Turacı, T., (2017). Exponential Domination and Bondage Numbers in Some Graceful Cyclic Structure, Nonlinear Dynamics and Systems Theory, 17(2), 139-149.
• [3] Aytac, A. and Atay, B., (2016). On Exponential Domination of Some Graphs, Nonlinear Dynamics and Systems Theory, 16(1), 12-19.
• [4] Ayta¸c, A., Odaba¸s, Z. N. and Turacı, T., (2011). The bondage number of some graphs, Comptes Rendus de Lacademie Bulgare des Sciences, vol. 64, no. 7, pp. 925930.
• [5] Ayta¸c, A., Turacı, T. and Odaba¸s, Z. N., (2013). On the bondage number of middle graphs, Mathematical Notes, vol. 93, no. 5-6, 795 801.
• [6] Ayta¸c, A. and Odaba¸s, Z. N., (2011). Residual Closeness of Wheels and Related Networks, Int. J. Found. Comput. Sci., 22, pp. 12291240.
• [7] Ayta¸c, A. and Berberler, Z. N., (2017). Binding Number and Wheel Related Graphs, Int. J. Found. Comput. Sci., 28(1), pp. 29-38.
• [8] Ayta¸c, A. and Berberler, Z. N.,(2017). Robustness of regular caterpillars, Int. J. Found. Comput. Sci., accepted.
• [9] Ayta¸c, A. and Odaba¸s Berberler, Z. N. Network robustness and residual closeness, RAIRO Operations Research, DOI: https://doi.org/10.1051/ro/2016071, appear.
• [10] Ayta¸c, A. and Odaba¸s, Z. N., (2010). Computing the rupture degree in composite graphs, Int. J.Found. Comput. Sci., 21(03), pp. 311-319.
• [11] Ayta¸c, A. and Odaba¸s, Z. N., (2009). On Computing The Vulnerability Of Some Graphs As Average, International Journal of Pure and Applied Mathematics, 55(1), pp. 137-146.
• [12] Berberler, M. E and Berberler, Z. N., (2017). Measuring the vulnerability in networks: a heuristic approach, ARS COMBINATORIA, accepted.
• [13] Chartrand, G. and Lesniak, L., (1986). Graphs and Digraphs, Second Edition, Wadsworth. Monterey.
• [14] Cormen, T., Leiserson, C. E. and Rivest, R. L., (1990). Introduction to Algorithms, The MIT Pres. (Fourth edition).
• [15] Cymen, M., Pilipczuk, M. and Skrekovski, R., (2010). Relation between Randic index and average distance of trees, Institute of Mathematics, Physics and Mechanics Jadranska, 48, Slovenia, 1130p.
• [16] Dankelmann, P., Day, D., Erwin, D., Mukwembi, S., Swart, H., (2009). Domination with exponential decay, Discrete Mathematics 309, pp. 5877-5883.
• [17] Gallian J. A., (2008). A dynamic survey of graph labeling, Elect. Jour. Combin. 15, DS6.
• [18] Hartsfield, N. and Ringel, Gerhard., (1990). Pearls in Graph Theory, Academic Press, INC.
• [19] Frucht, R. and Harary, F., (1970). On the corona two graphs, Aequationes Math., vol.4, pp. 322-325.
• [20] Haynes, T. W., Hedetniemi, S. T. and Slater, P. j. Fundamentals of Domination in Graphs, Marcel Dekker,Inc., New York.
• [21] Haynes, T. W., Henning, M. A., Van Der Merwe, L.C., (2007). The complementary product of two graphs, Bull. Instit. Combin. Appl. 51, pp. 21-30.
• [22] Haynes, T. W., Henning, M. A., Van Der Merwe, L. C., (2009). Domination and Total Domination in Complementary Prisms, J. Comb. Optim 18, pp. 23-37.
• [23] Hedetniemi, S. T. and Laskar, R. C., (1990). Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Mathematics, vol. 86, no. 1-3, pp. 257-277.
• [24] Odaba¸s, Z. N. and Ayta¸c, A., (2013). Residual closeness in cycles and related networks, Fundamenta Informaticae 124 (3), pp. 297-307.
• [25] Odaba¸s, Z.N. and Ayta¸c, A., (2012). Rupture Degree and Middle Graphs, Comptes Rendus De L Academie Bulgare Des Sciences 65(3), pp. 315-322.
• [26] Turacı, T. and Ayta¸c, V. Residual closeness of splitting networks, Ars Combinatoria ( accepted).
• [27] West, D. B., (2001). Introduction to Graph Theory (Second edition).