Please use this identifier to cite or link to this item: http://localhost:80/xmlui/handle/123456789/1154
Title: Computation of minimum d-hop connected dominating set of trees in O(n) time
Authors: Adhya, Amita Samanta
Mondal, Sukumar
Barman, Sambhu Charan
Dayap, Jonecis A.
Keywords: D-hop connected domination
Domination number
Trees
Issue Date: 2022
Publisher: Journal of Algebra Combinatorics Discrete Structures and Applications
Abstract: For a graph G = (V, E) and a fixed constant d ∈ N, a subset Dhd of the vertex set V is a d-hop connected dominating set of the graph G if each vertex t ∈ V is situated at most d-steps from at least one vertex z ∈ Dhd, that is, d(t, z) ≤ d, and the subgraph of G induced by Dhd is connected. If Dhd has minimum cardinality, then it is a minimum d-hop connected dominating set. In this paper, we present two O(n)-time algorithms for computing a minimum Dhd of trees with n vertices. We also design an algorithm to find the central vertices of a tree. Besides that, we also study some properties related to hop-domination on trees.
URI: http://111.93.204.14:8080/xmlui/handle/123456789/1154
ISSN: 2148-838X
Appears in Collections:Articles

Files in This Item:
File Description SizeFormat 
khop-tree-jacodsmath.pdf311.3 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.