Graphs with minimum fractional domatic number (Q6180653)

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\).