Skip to main content

Research Repository

Advanced Search

Graphs with minimum fractional domatic number

Gadouleau, Maximilien; Harms, Nathaniel; Mertzios, George B.; Zamaraev, Viktor

Graphs with minimum fractional domatic number Thumbnail


Nathaniel Harms

Viktor Zamaraev


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.


Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148.

Journal Article Type Article
Acceptance Date Oct 12, 2023
Online Publication Date Oct 28, 2023
Publication Date Jan 30, 2024
Deposit Date Nov 6, 2023
Publicly Available Date Nov 7, 2023
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 343
Pages 140-148
Keywords Applied Mathematics; Discrete Mathematics and Combinatorics
Public URL


You might also like

Downloadable Citations