WEIGHTED DOMINATION NUMBER OF CACTUS GRAPHS

DOI10.12732/IJAM.V29I4.1zbMATH Open1357.05116arXiv1604.06452OpenAlexW2963594876MaRDI QIDQ2959614FDOQ2959614

Authors: Tina Novak, Janez Žerovnik 

Publication date: 9 February 2017

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

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.

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

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

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)

Cited In (8)

• A linear time algorithm for weighted \(k\)-fair domination problem in cactus graphs
• Volume computation for sparse Boolean quadric relaxations
• The Hosoya polynomial of double weighted graphs
• Title not available (Why is that?)
• Weighted domination in triangle-free graphs
• A linear algorithm for finding a minimum dominating set in a cactus
• The \(k\)-power domination problem in weighted trees
• Fair domination number in cactus 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)