Graphs with equal domination and covering numbers

DOI10.1007/S10878-019-00454-6zbMATH Open1434.05112arXiv1802.09051OpenAlexW2788094261WikidataQ126984906 ScholiaQ126984906MaRDI QIDQ2292127FDOQ2292127

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• On graphs with equal domination and covering numbers
• Equivalence dominating sets in graphs
• Title not available (Why is that?)
• 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)