超图的匹配数和控制数及其相关极值超图刻画

发布时间：2020-04-02 23:11

【摘要】：在过去的半个世纪里,图论的研究随着科学技术的飞速发展而呈现出异常活跃的趋势.对图的控制数、匹配数和横贯数的研究是图论研究的一个重要方向,在计算机科学,生物系统,网络通讯,人工智能以及管理科学等学科领域中得到了广泛地应用.超图是最一般又最复杂的离散结构,可以看做是一般图(无向图)的一类自然推广.一般图上的关于控制数、匹配数和横贯数的问题已经得到了广泛而深入的探讨,但是超图上的相关问题是近些年来才被提出并得到研究的.在本文中,我们主要考虑了超图的控制数和匹配数之间的关系,并刻画了相关的极值超图.首先,我们给出了超图上控制数的一个上界,该上界与其匹配数相关.众所周知,控制数γ(H),匹配数v(H)和横贯数T(H)是超图的三个重要参数.Ryser猜想是讨论关于r-部超图的横贯数和匹配数之间关系的著名猜想,它表述为:对于任何一个r-部超图,都有T(H)≤(r-1)v(H).这一猜想是一个很困难的问题,对r ≥ 4的情形始终没有实质性的进展.受Ryser猜想的启发,我们考虑一致超图上控制数与匹配数之间的关系,证明了:如果H是一个r-一致超图,那么控制数和匹配数之间满足关系γ(H)≤(r-1)v(H),并通过构造一族超图说明超图的控制数的这一上界是紧的.其次,我们考虑达到上界γ(H)=(r-1)v(H)的极值交超图.由于超图的结构十分复杂,在一般情形下刻画满足γ(H)=(r-1)v(H)的超图显得非常困难.因此我们将目光聚焦在结构相对简单的线性交超图上.利用线性交超图的特性,我们通过3-阶有限射影平面构造出所有满足γ(H)=4的5-一致线性交超图.最后,我们研究了v(H)≥ 2的极值线性超图.回溯现有的满足等式γ(H)=(r-1)v(H)的超图,可以发现当r3时所刻画的极值超图都局限在交超图(v(H)=1)上,并且刻画已十分复杂.我们给出了 v(H)≥2的线性超图的一些特性,并刻画了满足γ(H)=6的2-匹配4-一致线性超图.
【图文】：

４＂逡逑肩逡逑图３．１．１示例[V逡逑引理３．１．４邋（邋［３４］）如果超图丑ｅ逦那么丑＇中的任意一条边至逡逑多含有一个度４点，并且△（丑＇）＝ｒ－１．逡逑引理３．１．５邋（［３４］）如果丑ｅ￡ｒ（ｒ＞３），那么片有一下一些特征：逡逑（ｉ）逦ｎ（Ｈ＇）邋＝邋（ｒ邋—邋ｌ）２邋—邋（ｒ邋—邋１）邋＋邋１．逡逑（ｉｉ）逦７（丑0邋＝邋１，并且把中的度－（ｒ－邋１）点都是Ｆ的一个控制集？逡逑（ｉｉｉ）逦３（ｒ邋—邋２）邋＜邋ｍ｛Ｈ＇）邋＜（ｒ邋—邋ｌ）２邋—邋（ｒ邋—邋１）邋＋邋１．逡逑进一步地，我们有以下这个引理．逡逑引理３．１．６设超图丑■？如果ｒ邋＞邋５，那么有ｍ（／Ｔ）邋２邋３ｒ－５．逡逑证明．根据引理３．１．５有ｍ（／Ｔ）２３ｒ－６．用反证法证明引理３．２．１的结逡逑论？假设ｍ（Ｈ＇）邋＝邋３ｒ邋－邋６？根据引理３．１．４可知，存在一个点ｗ邋＃rP罚ǔ螅В，

本文编号：2612562