Degree Sequence Conditions for Maximally Edge-Connected and Super Edge-Connected Hypergraphs

被引:0
作者
Shuang Zhao
Yingzhi Tian
Jixiang Meng
机构
[1] Xinjiang University,College of Mathematics and System Sciences
来源
Graphs and Combinatorics | 2020年 / 36卷
关键词
Degree sequence; Edge-connectivity; Hypergraph; Maximally edge-connected; Super edge-connected;
D O I
暂无
中图分类号
学科分类号
摘要
Let H be a connected hypergraph with minimum degree δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} and edge-connectivity λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda$$\end{document}. The hypergraph H is maximally edge-connected if λ=δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda = \delta$$\end{document}, and it is super edge-connected or super-λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda$$\end{document}, if every minimum edge-cut consists of edges incident with some vertex. There are several degree sequence conditions, for example, Goldsmith and White (Discrete Math 23: 31–36, 1978) and Bollobás (Discrete Math 28:321–323, 1979) etc. for maximally edge-connected graphs and super-λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda$$\end{document} graphs. In this paper, we generalize these and some other degree sequence conditions to uniform hypergraphs.
引用
收藏
页码:1065 / 1078
页数:13
相关论文
共 25 条
  • [1] Bollobás B(1979)On graphs with equal edge-connectivity and minimum degree Discrete Math. 28 321-323
  • [2] Chartrand G(1966)A graph-theoretic approach to a communications problem SIAM J. Appl. Math. 14 778-781
  • [3] Dankelmann P(1997)Degree sequence conditions for maxiamlly edge-connected graphs and digraphs J. Graph Theory 26 27-34
  • [4] Volkmann L(2016)Maximally edge-connected hypergraphs Discrete Math. 339 33-38
  • [5] Dankelmann P(2018)Connectivity in hypergraphs Can. Math. Bull. 61 252-271
  • [6] Meierling D(1978)On graphs with equal edge-connectivity and minimum degree Discrete Math. 23 31-36
  • [7] Dewar M(2013)Realizing degree sequences with Discrete Math. 313 1394-1400
  • [8] Pike D(2008)-edge-connected uniform hypergraphs Discrete Math. 308 3265-3296
  • [9] Proos J(1972)Maximally edge-connected and vertex-connected graphs and digraphs—a survey Theory Probab. Appl. 17 243-254
  • [10] Goldsmith DL(2019)Asymptonic formulas for the probability of Discrete Appl. Math 67 237-249