Combining the Concepts of Residual and Domination in Graphs

• Autorzy: Turacı Tufan , Aytaç Aysun

Identyfikatory

DOI

10.3233/FI-2019-1806

• Języki publikacji: EN

Abstrakty

EN

Let G = (V (G), E(G)) be a simple undirected graph. The domination and average lower domination numbers are vulnerability parameters of a graph. We have investigated a refinement that involves the residual domination and average lower residual domination numbers of these parameters. The lower residual domination number, denoted by γ_vk^R(G), is the minimum cardinality of dominating set in G that received from the graph G where the vertex v_k and all links of the vertex v_k are deleted. The residual domination number of graphs G is defined as [formula]. The average lower residual domination number of G is defined by [formula]. In this paper, we define the residual domination and the average lower residual domination numbers of a graph and we present the exact values, upper and lower bounds for some graph families.

Słowa kluczowe

EN

average lower residual domination number; domination number; graph vulnerability; network design; network communication; residual domination number

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 166, nr 4
• Strony: 379--392
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Turacı Tufan

• Department of Mathematics, Karabuk University, 78050 Karabuk, Turkey

autor

Aytaç Aysun

• Department of Mathematics, Ege University, 35100 İzmir, Turkey

Bibliografia

• [1] Frank H, Frisch I. Analysis and design of survivable networks. IEEE Transactions on Communication Technology, 1970. 18(5):501-519. doi:10.1109/TCOM.1970.1090419.
• [2] Mishkovski I, Biey M, Kocarev L. Vulnerability of complex networks. Communications in Nonlinear Science and Numerical Simulation, 2011. 16(1):341-349. doi:10.1016/j.cnsns.2010.03.018.
• [3] Newport KT, Varshney PK. Design of survivable communications networks under performance constraints. IEEE Transactions on Reliability, 1991. 40(4):433-440. doi:10.1109/24.93764.
• [4] Aytac A, Turaci T. Vertex vulnerability parameter of gear graphs. International Journal of Foundations of Computer Science, 2011. 22(05):1187-1195. doi:10.1142/S0129054111008635.
• [5] Chvátal V. Tough graphs and hamiltonian circuits. Discrete Mathematics, 1973. 5(3):215-228. doi:10.1016/0012-365X(73)90138-6.
• [6] Barefoot CA, Entringer R, Swart H. Vulnerability in graphs a comparative survey. J. Combin. Math. Combin. Comput, 1987. 1(38):13-22.
• [7] Haynes TW, Hedetniemi S, Slater P. Fundamentals of domination in graphs. Marcel Dekker, Inc, 1998. ISBN-10:0824700333, 13:978-0824700331.
• [8] Aytac A, Odabas ZN. Residual closeness of wheels and related networks. International Journal of Foundations of Computer Science, 2011. 22(05):1229-1240. doi:10.1142/S0129054111008660.
• [9] Dangalchev C. Residual closeness in networks. Physica A: Statistical Mechanics and its Applications, 2006. 365(2):556-564. doi:10.1016/j.physa.2005.12.020.
• [10] Turaci T, Okten M. Vulnerability of mycielski graphs via residual closeness. Ars Combinatoria, 2015. 118:419-427.
• [11] Beineke LW, Oellermann OR, Pippert RE. The average connectivity of a graph. Discrete mathematics, 2002. 252(1-3):31-45. doi:10.1016/S0012-365X(01)00180-7.
• [12] Blidia M, Chellali M, Maffray F. On average lower independence and domination numbers in graphs. Discrete mathematics, 2005. 295(1-3):1-11. doi:10.1016/j.disc.2004.12.006.
• [13] Henning MA. Trees with equal average domination and independent domination numbers. Ars Combinatoria, 2004. 71:305-318.
• [14] Tuncel Golpek H, Turaci T, Coskun B. The Average Lower Domination Number and Some Results of Complementary Prisms and Graph Join. J. Adv. Res. Appl. Math, 2015. 7(1):52-61. doi:10.5373/jaram.2056.053014.
• [15] Aslan E. The average lower connectivity of graphs. Journal of Applied Mathematics, 2014. 2014. doi:10.1155/2014/807834.
• [16] Turaci T. On the average lower bondage number of a graph. RAIRO-Operations Research, 2016. 50(4-5):1003-1012. doi:10.1051/ro/2015062.
• [17] Turaci T, Aslan E. The average lower reinforcement number of a graph. RAIRO-Theoretical Informatics and Applications, 2016. 50(2):135-144. doi:10.1051/ita/2016015.
• [18] Chartrand G, Lesniak L, Zhang P. Graphs & digraphs. Chapman and Hall/CRC, 2010. ISBN:1439826277, 9781439826270.
• [19] Berge C. Graphs and hypergraphs. North-Holland Pub. Co., 1973.
• [20] Liu CL. Introduction to combinatorial mathematics. McGraw-Hill, 1968. ISBN: 0070381240, 9780070381247.
• [21] Henning MA, Oellermann OR. The average connectivity of a digraph. Discrete Applied Mathematics, 2004. 140(1-3):143-153. doi:10.1016/j.dam.2003.04.003.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).