Graphs with equal domination and covering numbers

DOI10.1007/S10878-019-00454-6MaRDI QIDQ2292127zbMATH OpenOpenAlexWikidataFDO

Authors Andrzej Lingas, Mateusz Miotk, Jerzy Topp, Paweł Żyliński

Publication date 3 February 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

independencecoveringdominationguarding grid

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A dominating set of a graph $G$ is a set $Dsubseteq{V}_G$ such that every vertex in $V_G-D$ is adjacent to at least one vertex in $D$, and the domination number $gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. A set $Csubseteq{V}_G$ is a covering set of $G$ if every edge of $G$ has at least one vertex in $C$. The covering number $$ of $G$ is the minimum cardinality of a covering set of $G$. The set of connected graphs $G$ for which $$ is denoted by $$, while $calB$ denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to $$ and $calB$. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to $calB$, and, as a side result, we conclude that the algorithm of Arumugam et al. [2] allows to recognize all the graphs belonging to the set $$ in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that this problem can be solved in $O(nlogn+m)$ time, where $n$ is the number of line segments of the input grid and $m$ is the number of its intersection points.

Recommendations

• Characterization of graphs with equal domination and covering number
• scientific article; zbMATH DE number 734463
• On graphs with equal domination and covering numbers
• Paired-domination in graphs
• Bipartization of graphs

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 3747181 (Why is no real title available?)
• scientific article; zbMATH DE number 1043910 (Why is no real title available?)
• scientific article; zbMATH DE number 817208 (Why is no real title available?)
• scientific article; zbMATH DE number 843316 (Why is no real title available?)
• scientific article; zbMATH DE number 6257577 (Why is no real title available?)
• A characterization of graphs with equal domination number and vertex cover number
• A constructive characterization of trees with equal total domination and disjunctive domination numbers
• A note on the edge Roman domination in trees
• An improved algorithm for computing a shortest watchman route for lines
• Approximability issues of guarding a set of segments
• Bipartization of graphs
• Changing and unchanging domination: A classification
• Changing and unchanging of the domination number of a graph
• Characterization of graphs with equal domination and covering number
• Domination-balanced graphs
• Equality of domination and transversal numbers in hypergraphs
• Italian domination in trees
• On gallery watchmen in grids
• On graphs having domination number half their order
• On graphs with equal domination and covering numbers
• Orthogonal segment stabbing
• Some variations of perfect graphs
• Strong equality of Roman and weak Roman domination in trees
• THE MINIMUM GUARDING TREE PROBLEM
• Well irredundant graphs

Cited in

(9)

• On graphs with equal domination and covering numbers
• Equivalence dominating sets in graphs
• scientific article; zbMATH DE number 5016689 (Why is no real title available?)
• On the equivalence covering number of splitgraphs
• Characterization of graphs with equal domination and covering number
• Bipartite graphs with close domination and \(k\)-domination numbers
• On graphs with equal domination and connected domination numbers
• Multiple domination
• Bipartization of graphs

This page was built for publication: Graphs with equal domination and covering numbers

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