DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

Y. Tian

Yingzhi Tian

Xinjiang University

email: tianyzhxj@163.com

H.-J. Lai

Hong-Jian Lai

West Virginia University

email: Hong-jian.Lai@mail.wvu.edu

J. Meng

Jixiang Meng

Xinjiang
University

email: mjx@xju.edu.cn

M. Xu

Murong Xu

The Ohio State University

email: xu.3646@osu.edu

Title:

On the sizes of $(k,l)$-edge-maximal $r$-uniform hypergraphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(1) (2023) 179-194

Received: 2019-12-27 , Revised: 2020-08-19 , Accepted: 2020-08-19 , Available online: 2020-09-30 , https://doi.org/10.7151/dmgt.2362

Abstract:

Let $H=(V,E)$ be a hypergraph, where $V$ is a set of vertices and $E$ is a set of non-empty subsets of $V$ called edges. If all edges of $H$ have the same cardinality $r$, then $H$ is an $r$-uniform hypergraph; if $E$ consists of all $r$-subsets of $V$, then $H$ is a complete $r$-uniform hypergraph, denoted by $K_n^r$, where $n=|V|.$ An $r$-uniform hypergraph $H=(V,E)$ is $(k,l)$-edge-maximal if every subhypergraph $H'$ of $H$ with $|V(H')|\geq l$ has edge-connectivity at most $k$, but for any edge $e\in E(K_n^r)\setminus E(H)$, $H+e$ contains at least one subhypergraph $H''$ with $|V(H'')|\geq l$ and edge-connectivity at least $k+1$. In this paper, we obtain the lower bounds and the upper bounds of the sizes of $(k,l)$-edge-maximal hypergraphs. Furthermore, we show that these bounds are best possible.

Keywords:

edge-connectivity, $(k,l)$-edge-maximal hypergraphs, $r$-uniform hypergraphs

References:

  1. M.A. Bahmanian and M. Šajna, Connection and separation in hypergraphs, Theory Appl. Graphs 2 (2015) Article 5.
    https://doi.org/10.20429/tag.2015.020205
  2. F.T. Boesch and J.A.M. McHuge, An edge extremal result for subcohesion, J. Combin. Theory Ser. B 38 (1985) 1–7.
    https://doi.org/10.1016/0095-8956(85)90087-5
  3. J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer, Berlin, 2008).
  4. M. Dewar, D. Pike and J. Proos, Connectivity in hypergraphs, Canad. Math. Bull. 61 (2018) 252–271.
    https://doi.org/10.4153/CMB-2018-005-9
  5. H.-J. Lai, The size of strength-maximal graphs, J. Graph Theory 14 (1990) 187–197.
    https://doi.org/10.1002/jgt.3190140207
  6. H.-J. Lai and C.-Z. Zhang, Edge-maximal $(k,i)$-graphs, J. Graph Theory 18 (1994) 227–240.
    https://doi.org/10.1002/jgt.3190180303
  7. W. Mader, Minimale $n$-fach kantenzusammenhängende Graphen, Math. Ann. 191 (1971) 21–28.
    https://doi.org/10.1007/BF01433466
  8. D.W. Matula, $k$-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22 (1972) 459–480.
    https://doi.org/10.1137/0122040
  9. Y.Z. Tian, L.Q. Xu, H.-J. Lai and J.X. Meng, On the sizes of $k$-edge-maximal $r$-uniform hypergraphs (2018).
    arXiv: 1802.08843v3

Close