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

domatic numberdomination 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.

Review text

For a graph \(G\) and a natural number \(s\), let \(f(G,s)\) be the maximum number of not necessarily distinct dominating sets of graph \(G\) such that every vertex is contained in at most \(s\) of them. Then the fractional domatic number \(FD(G)\), is the supremum of \(f(G,s)/s\). It is easy to see that \(FD(G)=1\) whenever \(G\) has an isolated vertex. Otherwise, \(FD(G)\geq 2\). The main result of the paper gives a characterization of graphs with \(FD(G)=2\) as graphs with minimal degree \(1\) or a connected component isomorphic to a \(4\)-cycle. In the proof, the authors use the concept of \((k,s)\)-configuration of graph \(G\), which means a collection of \(k\) not necessarily disjoint dominating sets of \(G\) such that each vertex is contained in at most \(s\) of these sets. The main strategy is to reduce the graph into a union of smaller graphs. If the graph is not \(2\)-connected, the concept of a dumbbell graph with a handle is used for inductive reduction of a larger graph to smaller ones. Different cases are then carefully analyzed to obtain full proof. In the conclusion, a conjecture is posed that there are no graphs with \(2<FD(G)<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

• 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
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• 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)