Bipartization of graphs

DOI10.1007/S00373-019-02068-5MaRDI QIDQ2334080zbMATH OpenOpenAlexFDO

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

Publication date 6 November 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bipartite graphbipartizationdomination number

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

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$. In this paper we provide a new characterization of bipartite graphs whose domination number is equal to the cardinality of its smaller partite set. Our characterization is based upon a new graph operation.

Recommendations

• Domination in partitioned graphs
• Dominating sets for split and bipartite graphs
• Bichromaticity and domatic number of a bipartite graph
• Bipartite graphs with close domination and \(k\)-domination numbers
• A note on global domination in graphs

Cites work

• A characterization of graphs with equal domination number and vertex cover number
• Characterization of graphs with equal domination and covering number
• Equality of domination and transversal numbers in hypergraphs
• Graphs with equal domination and covering numbers
• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 817208 (Why is no real title available?)

Cited in

(23)

• Bipartable graphs
• Bilinear and trilinear partitions of a graph
• Graph bisection revisited
• Graphs with equal domination and covering numbers
• Y X domination in bipartite graphs
• Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
• Complement free domination number of a bipartite graph
• On the characterization of the maximal connected bipartite graphs with given domination number
• 2-domination in bipartite graphs with odd independence number
• Very cost effective bipartitions in graphs
• scientific article; zbMATH DE number 5348111 (Why is no real title available?)
• Bichromaticity and domatic number of a bipartite graph
• scientific article; zbMATH DE number 1156679 (Why is no real title available?)
• Bipartite theory on neighbourhood dominating and global dominating sets of a graph
• Domination in partitioned graphs
• BIPARTITIONING INTO OVERLAPPING SETS
• A note on X-domatic number of a bipartite graph
• Successive partition of edges of bipartite graph into matchings
• Bipartite Domination in Graphs
• scientific article; zbMATH DE number 6469239 (Why is no real title available?)
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 7324127 (Why is no real title available?)
• Bipartitions of oriented graphs

This page was built for publication: Bipartization of graphs

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