Research article

On the fractional total domatic numbers of incidence graphs

  • Received: 21 August 2022 Revised: 02 December 2022 Accepted: 08 December 2022 Published: 20 February 2023
  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1133) PDF downloads(112) Cited by(0)

Article outline

Figures and Tables

Figures(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog