Graphs with minimum fractional domatic number

DOI10.1016/J.DAM.2023.10.020MaRDI QIDQ6180653zbMATH OpenFDO

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

Publication date 2 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• Publication:3032298
• Fractional domatic, idomatic, and total domatic numbers of a graph
• On domatic number of graphs
• scientific article; zbMATH DE number 1161319
• Minimal dominating sets in maximum domatic partitions

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• A Study on r-Configurations---A Resource Assignment Problem on Graphs
• Deploying robots with two sensors in \(K_{1,6}\)-free graphs
• Fractional domatic, idomatic, and total domatic numbers of a graph
• Non-Separable and Planar Graphs
• The price of being near-sighted

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)