WEIGHTED DOMINATION NUMBER OF CACTUS GRAPHS

DOI10.12732/IJAM.V29I4.1MaRDI QIDQ2959614zbMATH OpenOpenAlexFDO

Authors Tina Novak, Janez Žerovnik

Publication date 9 February 2017

Published in International Journal of Apllied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.06452

zbMATH Keywords

cactus graphDFS structureweighted domination problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Abstract: In the paper, we write 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.

Recommendations

• scientific article; zbMATH DE number 7144751
• On the p-domination number of cactus graphs
• A classification of cactus graphs according to their domination number
• A classification of cactus graphs according to their total domination number
• scientific article; zbMATH DE number 1743970
• Weighted domination of cocomparability graphs
• Weighted domination on cocomparability graphs
• Weighted domination in triangle-free graphs
• Fair domination number in cactus graphs
• scientific article; zbMATH DE number 5238170

Cited in

(8)

• A linear time algorithm for weighted \(k\)-fair domination problem in cactus graphs
• A linear algorithm for finding a minimum dominating set in a cactus
• The Hosoya polynomial of double weighted graphs
• The \(k\)-power domination problem in weighted trees
• scientific article; zbMATH DE number 7144751 (Why is no real title available?)
• Fair domination number in cactus graphs
• Volume computation for sparse Boolean quadric relaxations
• Weighted domination in triangle-free graphs

This page was built for publication: WEIGHTED DOMINATION NUMBER OF CACTUS GRAPHS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959614)