Graphs with minimum fractional domatic number

DOI10.1016/J.DAM.2023.10.020arXiv2302.11668MaRDI QIDQ6180653FDOQ6180653

Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios, Victor Zamaraev

Publication date: 2 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly the graphs that contain an isolated vertex. Furthermore, it is known that all other graphs have fractional domatic number at least 2. In this note we characterize graphs with fractional domatic number 2. More specifically, we show that a graph without isolated vertices has fractional domatic number 2 if and only if it has a vertex of degree 1 or a connected component isomorphic to a 4-cycle. We conjecture that if the fractional domatic number is more than 2, then it is at least 7/3.

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

zbMATH Keywords

domination numberdomatic numberfractional domatic number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Non-Separable and Planar Graphs
• Deploying Robots With Two Sensors inK_{1, 6}-Free Graphs
• The price of being near-sighted
• A Study on r-Configurations---A Resource Assignment Problem on Graphs
• Fractional Domatic, Idomatic, and Total Domatic Numbers of a Graph

This page was built for publication: Graphs with minimum fractional domatic number

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