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


Authors

Nathaniel Harms

Viktor Zamaraev



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.

Citation

Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. https://doi.org/10.1016/j.dam.2023.10.020

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
DOI https://doi.org/10.1016/j.dam.2023.10.020
Keywords Applied Mathematics; Discrete Mathematics and Combinatorics
Public URL https://durham-repository.worktribe.com/output/1897822

Files




You might also like



Downloadable Citations