
Number of Journals | 34 |
Number of Issues | 1,306 |
Number of Articles | 9,427 |
Article View | 9,189,640 |
PDF Download | 5,621,872 |
k-Adjacency Domination in Graphs | ||
پدافند الکترونیکی و سایبری | ||
Volume 9, Issue 3 - Serial Number 35, December 2021, Pages 125-131 PDF (610.79 K) | ||
Document Type: Original Article | ||
Author | ||
Davood Bakhshesh* | ||
Assistant Professor, Department of Computer Science, Bojnourd University, Bojnourd, Iran | ||
Receive Date: 16 December 2020, Revise Date: 01 February 2021, Accept Date: 25 February 2021 | ||
Abstract | ||
Let be a simple and undirected graph with vertex set . A set is called a dominating set of if every vertex outside is adjacent to at least one vertex of . For any integer , a dominating set is called a -adjacency dominating set of if the induced subgraph contains at least one vertex of degree at most . The minimum cardinality of a - adjacency dominating set of is called the - adjacency domination number of that is denoted by . In this paper, the study of - adjacency domination in graphs is initiated, and exact values and some bounds on the - adjacency domination number of a given graph are presented. Furthermore, it is shown that there is a polynomial-time algorithm that computes the -adjacency domination number of a given tree. Moreover, it is proven that the decision problem associated to the -adjacency domination is NP-complete for bipartite graphs. | ||
Keywords | ||
Dominating set; Graph; Domination number | ||
References | ||
[1]. T. W. Haynes, S. Hedetniemi, and P. Slater, “Fundamentals of dominationin graphs,” CRC Press, 1998.## [2]. M. Rajaati Bavil Olyaei and M. R. Hooshmandasl, “Generating Tree Decomposition of Graphs with Imperialist Competitive Algorithm for Use in Secret Sharing Scheme,” Jourrnal of Electronical & Cyber Defence, vol. 7, no. 3, pp. 105-111, 2019. (In Persian).## [3]. N. Biggs, “Perfect codes in graphs,” J. Comb. Theory. B., vol. 15, no. 3, pp. 289-296, 1973.## [4]. S. Hamid and S. Balamurugan, “Isolate domination in graphs,” Arab Journal of Mathematical Sciences, vol. 22, no. 2, pp. 232- 241, 2016.## [5]. N. J. Rad, “Some notes on the isolate domination in graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 14, no. 2, pp. 112-117, 2017.## [6]. G. Rajasekar and A. Jeslet Kani Bala, “𝑘-Isolate domination number of simple graphs,” Malaya Journal of Matematik, vol. S, no. 1, pp. 113-115, 2019.## [7]. E. Cockayne, S. Goodman, S. Hedetniemi, “A linear algorithm for the domination number of a tree,” Inform. Process. Lett., vol. 4, no. 2, pp. 41-44, 1975.## [8]. M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-## | ||
Statistics Article View: 332 PDF Download: 314 |