2015/06/24 by Cristina Bazgan, Ljiljana Branković, Ljiljana Brankovic +17
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1506.07260
arxiv created 2015/06/24 · openalex publication_date 2015/06/24 · arxiv updated 2015/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a full classification of the related maximisation and minimisation problems, as well as the related parameterised problems, on general graphs and on graphs of bounded degree, and we also study planar graphs.