WEIGHTED DOMINATION NUMBER OF CACTUS GRAPHS
Tina Novak1, Janez Žerovnik2
1,2Faculty of Mechanical Engineering
University of Ljubljana
Ljubljana, 1000, SLOVENIA
Abstract. In this paper we propose a linear algorithm for calculating the weighted domination number of a vertex-weighted cactus. The algorithm is based on the well known depth first search (DFS) structure. Our algorithm needs less than 12n+5b additions and 9n+2b min-operations where n is the number of vertices and b is the number of blocks in the cactus.
AMS Subject Classification: 05C69, 05C22, 05C85
Key Words and Phrases: weighted domination problem, cactus graph, DFS structure


Download full article from here (pdf format).

DOI: 10.12732/ijam.v29i4.1

Volume: 29
Issue: 4
Year: 2016