Bipartite graphs with close domination and k-domination numbers

DOI10.1515/MATH-2020-0047MaRDI QIDQ2053423zbMATH OpenOpenAlexFDO

Authors Gülnaz Boruzanlı Ekinci, Csilla Bujtás

Publication date 29 November 2021

Published in Open Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(k\)-domination numbercomputational complexitydomination numberhereditary propertyTC-numbervertex-edge cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $k$ be a positive integer and let $G$ be a graph with vertex set $V(G)$. A subset $DsubseteqV(G)$ is a $k$-dominating set if every vertex outside $D$ is adjacent to at least $k$ vertices in $D$. The $k$-domination number $gamm{a}_k(G)$ is the minimum cardinality of a $k$-dominating set in $G$. For any graph $G$, we know that $gamm{a}_k(G)geqgamma(G)+k-2$ where $Delta(G)geqkgeq2$ and this bound is sharp for every $kgeq2$. In this paper, we characterize bipartite graphs satisfying the equality for $kgeq3$ and present a necessary and sufficient condition for a bipartite graph to satisfy the equality hereditarily when $k=3$. We also prove that the problem of deciding whether a graph satisfies the given equality is NP-hard in general.

Recommendations

• A note on bipartite graphs whose \([1,k]\)-domination number equal to their number of vertices
• 2-domination in bipartite graphs with odd independence number
• The algorithmic complexity of \(k\)-domatic partition of graphs
• A bound on the k-domination number of a graph.
• Independence and 2-domination in bipartite graphs

Cites work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• A characterization of trees with equal 2-domination and 2-independence numbers
• A note on the k-domination number of a graph
• Bounds for the 2-domination number of toroidal grid graphs
• Bounds on the 2-domination number
• Characterization of graphs with equal domination and covering number
• Characterizations of trees with equal paired and double domination numbers
• Claw-free graphs with equal 2-domination and domination numbers
• Equality of domination and transversal numbers in hypergraphs
• Graphs with equal domination and covering numbers
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 3914371 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2544 (Why is no real title available?)
• scientific article; zbMATH DE number 5806 (Why is no real title available?)
• scientific article; zbMATH DE number 817208 (Why is no real title available?)
• On \(k\)-domination and \(j\)-independence in graphs
• On graphs with equal domination and 2-domination numbers
• On the k-domination number, the domination number and the cycle of length four
• Onk-domination and minimum degree in graphs
• Some variations of perfect graphs

Cited in

(15)

• Bipartization of graphs
• On bipartite graphs whose interval space is a closed join space
• Perfect graphs for domination games
• \(k\)-domination and total \(k\)-domination numbers in catacondensed hexagonal systems
• The algorithmic complexity of \(k\)-domatic partition of graphs
• 2-domination in bipartite graphs with odd independence number
• Multiple domination
• scientific article; zbMATH DE number 731842 (Why is no real title available?)
• A note on domination in bipartite graphs
• Almost well-dominated bipartite graphs with minimum degree at least two
• On the complexity of \(k\)-step and \(k\)-hop dominating sets in graphs
• Characterization of outerplanar graphs with equal 2-domination and domination numbers
• A note on bipartite graphs whose \([1,k]\)-domination number equal to their number of vertices
• Independence and 2-domination in bipartite graphs
• On the equality of domination number and 2-domination number

This page was built for publication: Bipartite graphs with close domination and \(k\)-domination numbers

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