For two nondecreasing sequences $d=\left(d_1, d_2, \cdots, d_n\right)$ and $d^{\prime}=\left(d_1^{\prime}, d_2^{\prime}, \cdots, d_n^{\prime}\right)$ of nonnegative integers, we say that $d^{\prime}$ majorizes $d$, denoted by $d^{\prime} \geqslant d$, if $d_i^{\prime} \geqslant d_i$ for $1 \leqslant i \leqslant n$. An $r$-uniform hypergraphic sequence $d=\left(d_1, d_2, \cdots, d_n\right)$ is forcibly $k$-connected if every $r$-uniform hypergraph with degree sequence $d$ is $k$-connected. In this paper, we give a sufficient condition for an $r$-uniform hypergraphic sequence to be forcibly $k$-connected and observe that if an $r$-uniform hypergraphic sequence $d$ satisfies the condition (which implies $d$ is forcibly $k$-connected); then, any $r$-uniform hypergraphic sequence $d^{\prime} \geqslant d$ also satisfies the condition. As a corollary, we obtain the condition of Bondy for forcibly $k$-connected graphic sequences.
Xue-Mei Liu, Ji-Xiang Meng, Ying-Zhi Tian
. On Forcibly k-Connected Uniform Hypergraphic Sequences[J]. Journal of the Operations Research Society of China, 2025
, 13(4)
: 1205
-1215
.
DOI: 10.1007/s40305-023-00509-w
[1] Berge, C.: Hypergraphs: Combinatorics of Finite Sets. North-Holland, Amsterdam (1989)
[2] Dewar, M., Pike, D., Proos, J.: Connectivity in hypergraphs. Can. Math. Bull. 61, 252–271 (2018)
[3] Dankelmann, P., Meierling, D.: Maximally edge-connected hypergraphs. Discret. Math. 339, 33–38 (2016)
[4] Shan, E., Zhao, J., Kang, L.: Maximally connected p-partite uniform hypergraphs. Discret. Appl. Math. 264, 188–195 (2019)
[5] Tong, L., Shan, E.: Sufficient conditions for maximally edge-connected hypergraphs. J. Oper. Res. Soc. China. 9, 119–129 (2021)
[6] Zhao, S., Meng, J.: Sufficient conditions for hypergraphs to be maximally edge-connected hypergraphs. Appl. Math. Comput. 333, 362–368 (2018)
[7] Zhao, S., Tian, Y., Meng, J.: Degree sequence conditions for maximally edge-connected and super edge-connected hypergraphs. Graphs Comb. 36, 1065–1078 (2020)
[8] Chvátal, V.: On Hamilton’s ideals. J. Comb. Theory Ser. B. 12, 163–168 (1972)
[9] Nash-Williams, C.St.J.A.: Hamiltonian arcs and circuits. Lecture Notes in Math. Recent Trends in Graph Theory, pp. 197–210 (1970)
[10] Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. 2, 68–81 (1952)
[11] Boesch, F.T.: The strongest monotone degree condition for n-connectedness of a graph. J. Comb. Theory Ser. B. 16, 162–165 (1974)
[12] Bondy, J.A.: Properties of graphs with constraints on degrees. Studia Sci. Math. Hungar. 4, 473–475 (1969)
[13] Bauer, D., Hakimi, S.L., Kahl, N., Schmeichel, E.: Sufficient degree conditions for k-edgeconnectedness of a graph. Networks. 54, 95–98 (2009)
[14] Kriesell, M.: Degree sequences and edge connectivity. Abh. Math. Semin. Univ. Hambg. 87, 343–355 (2017)
[15] Yin, J., Guo, J.: A new sufficient degree condition for a graphic sequence to be forcibly k-edgeconnected. Acta Math. Appl. Sinica, Engl. Ser. 38, 223–228 (2022)
[16] Liu, X., Meng, J., Tian, Y.: On forcibly k-edge-connected and forcibly super edge-connected uniform hypergraphic sequences. J. Supercomput. 79, 15980–15996 (2023)
[17] Liu, X., Meng, J., Tian, Y.: On forcibly k-connected and forcibly k-arc-connected digraphic sequences. Discret. Appl. Math. 321, 10–18 (2022)
