For a hypergraph $ H $ with vertex set $ X $ and edge set $ Y $, the incidence graph of hypergraph $ H $ is a bipartite graph $ I(H) = (X, Y, E) $, where $ xy\in E $ if and only if $ x\in X $, $ y\in Y $ and $ x\in y $. A total dominating set of graph $ G $ is a vertex subset that intersects every open neighborhood of $ G $. Let $ \mathscr{M} $ be a family of (not necessarily distinct) total dominating sets of $ G $ and $ r_{\mathscr{M}} $ be the maximum times that any vertex of $ G $ appears in $ \mathscr{M} $. The fractional domatic number $ G $ is defined as $ FTD(G) = \sup_{\mathscr{M}}\frac{|\mathscr{M}|}{r_{\mathscr{M}}} $. In 2018, Goddard and Henning showed that the incidence graph of every complete $ k $-uniform hypergraph $ H $ with order $ n $ has $ FTD(I(H)) = \frac{n}{n-k+1} $ when $ n\geq 2k\geq 4 $. We extend the result to the range $ n > k\geq 2 $. More generally, we prove that every balanced $ n $-partite complete $ k $-uniform hypergraph $ H $ has $ FTD(I(H)) = \frac{n}{n-k+1} $ when $ n\geq k $ and $ H\ncong K_n^{(n)} $, where $ FTD(I(K_n^{(n)})) = 1 $.
Citation: Yameng Zhang, Xia Zhang. On the fractional total domatic numbers of incidence graphs[J]. Mathematical Modelling and Control, 2023, 3(1): 73-79. doi: 10.3934/mmc.2023007
For a hypergraph $ H $ with vertex set $ X $ and edge set $ Y $, the incidence graph of hypergraph $ H $ is a bipartite graph $ I(H) = (X, Y, E) $, where $ xy\in E $ if and only if $ x\in X $, $ y\in Y $ and $ x\in y $. A total dominating set of graph $ G $ is a vertex subset that intersects every open neighborhood of $ G $. Let $ \mathscr{M} $ be a family of (not necessarily distinct) total dominating sets of $ G $ and $ r_{\mathscr{M}} $ be the maximum times that any vertex of $ G $ appears in $ \mathscr{M} $. The fractional domatic number $ G $ is defined as $ FTD(G) = \sup_{\mathscr{M}}\frac{|\mathscr{M}|}{r_{\mathscr{M}}} $. In 2018, Goddard and Henning showed that the incidence graph of every complete $ k $-uniform hypergraph $ H $ with order $ n $ has $ FTD(I(H)) = \frac{n}{n-k+1} $ when $ n\geq 2k\geq 4 $. We extend the result to the range $ n > k\geq 2 $. More generally, we prove that every balanced $ n $-partite complete $ k $-uniform hypergraph $ H $ has $ FTD(I(H)) = \frac{n}{n-k+1} $ when $ n\geq k $ and $ H\ncong K_n^{(n)} $, where $ FTD(I(K_n^{(n)})) = 1 $.
[1] | W. Goddard, M. Henning, Thoroughly dispersed colorings, J. Graph Theor., 88 (2018), 174–191. http://doi.org/10.1002/jgt.22204 doi: 10.1002/jgt.22204 |
[2] | M. Henning, A. Yeo, A note on fractional disjoint transversals in hypergraphs, Discrete Math., 340 (2017), 2349–2354. http://doi.org/10.1016/j.disc.2017.05.001 doi: 10.1016/j.disc.2017.05.001 |
[3] | B. Bollobás, D. Pritchard, T. Rothvoß, A. Scott, Cover-decomposition and polychromatic numbers, SIAM Journal of Discrete Mathematics, 27 (2013), 240–256. http://doi.org/10.1137/110856332 doi: 10.1137/110856332 |
[4] | A. Kostochka, D. Woodall, Density conditions for panchromatic colourings of hypergraphs, Combinatorica, 21 (2001), 515–541. http://doi.org/10.1007/s004930100011 doi: 10.1007/s004930100011 |
[5] | T. Li, X. Zhang, Polychromatic colorings and cover decompositions of hypergraphs, Appl. Math. Comput., 339 (2018), 153–157. http://doi.org/10.1016/j.amc.2018.07.019 doi: 10.1016/j.amc.2018.07.019 |
[6] | M. Henning, A. Yeo, $2$-colorings in $k$-regular $k$-uniform hypergraphs, Eur. J. Combin., 34 (2013), 1192–1202. http://doi.org/10.1016/j.ejc.2013.04.005 doi: 10.1016/j.ejc.2013.04.005 |
[7] | Z. Jiang, J. Yue, X. Zhang, Polychromatic colorings of hypergraphs with high balance, AIMS Mathematics, 5 (2020), 3010–3018. http://doi.org/10.3934/math.2020195 doi: 10.3934/math.2020195 |
[8] | B. Chen, J. Kim, M. Tait, J. Verstraete, On coupon colorings of graphs, Discrete Appl. Math., 193 (2015), 94–101. http://doi.org/10.1016/j.dam.2015.04.026 doi: 10.1016/j.dam.2015.04.026 |
[9] | W. Goddard, M. Henning, Fractional Domatic, Idomatic, and Total Domatic Numbers of a Graph. In: Haynes, T.W., Hedetniemi, S.T., Henning, M.A. (eds) Structures of Domination in Graphs, Developments in Mathematics, 66 (2021), 79–99. Springer, Cham. http://doi.org/10.1007/978-3-030-58892-2_4 |