兰州大学机构库 >数学与统计学院
点传递图的p因子临界性与s限制边连通性
Alternative TitleThe p-factor-criticality and s-restricted edge-connectivity of vertex-transitive graphs
孙午阳
Thesis Advisor张和平
2014-05-27
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
Keyword点传递图 3因子临界性 4因子临界性 s限制边连通度 超s限制边连通的
Abstract本文的第一部分工作是研究点传递图的p因子临界性. p因子临界图的概念是Favaron和Yu 独立地提出来的. 从一个顶点数为n的图中删除任意p个顶点而得到的图仍具有完美 匹配, 其中p是与n具有相同奇偶性的正整数, 则称该图是p因子临界的. 1因子 临界图与2因子临界图分别就是我们通常所说的因子临界图与双临界图. 在Lovasz与Plummer 所著的专著《Matching Theory》中, 已经指出一个连通的顶点数为奇数的点传递图是因子临界的, 一个连通非二部的顶点数为 偶数的点传递图是双临界的. 我们做了进一步的考虑, 考虑了当p=3,4时点传递图的p因子临界性. 首先, 本文对点传递图的3因子临界性给出了一个清楚的刻画: 一个连通的顶点数为至少是3的奇数的 点传递图除圈外都是3因子临界的. 该结果比Miklavic和Sparl给出的一个连通的 顶点数为奇数且至少为3的交换群上的Cayley图要么是一个圈, 要么是1.5可扩的这个结果 更具有一般性, 并且是一个更强的结果. 然后, 本文又刻画了点传递图的4因子临界性. 我们证明了一个连通的顶点数为偶数且至少为6的非二部的点传递图是4因子临界的当且仅当它的度 至少为5. 利用我们的这个结果, 可以推出 连通非二部、顶点数为偶数且度大于4的Cayley图都是2可扩的. 这解决了Chan, Chen和Yu提出的刻画所有2可扩的Cayley图这个公开问题的很大一部分. 我们在研究点传递图的~$p$~因子临界性的过程中, 应用了许多点传递图的s限制边连通性的结果. 为了方便研究点传递图更高阶的p因子临界性, 本文也专门对点传递图的s限制边连通性做了研究. 图的s限制边连通度这个概念是由Fabrega和Fiol提出, 可以用来更好地分析网络的可靠性. 设G是一个连通图, s是一个 正整数. 我们称G的一个边割F为它的s限制边割, 如果G-F的每一个分支都至少含有s个顶点. 对于一个含有s限制边割的图G, 称其大小最小的s限制边割的大小为它的s限制边连通度, 记为\lambda_{s}(G). 令\xi_{s}(G)=min{d(X): X\subseteq V(G),|X|=s并且G[X]是连通的}. 已经被证明, 对于很多图都有\lambda_{s}≤\xi_{s}. 一个连通图G称作超s限制边连通的, 简称超\lambda_{s}的, 如果\lambda_{s}(G)=\xi_{s}(G)并且G的每一个s限制边割都孤立了一个具有s个顶点的分支. 关于图的s限制边连通性的研究, 近十年来已经吸引到了许多计算机工作者和数学工作者 的兴趣. 对于点传递图的s限制边连通性, 王应前证明了一个连通且度至少为3、围长至少为~5~的点传递图是 超\lambda_{2}的. 后来, 欧见平等和杨卫华等又研究了 点传递图的3限制边连通性, 指出一个连通且度至少为4围长至少为5的点传递图是超\lambda_{3}的. 我们对更大的整数s, 进一步地研究了围长较大的点传递图的超~$s$~限制边连通性. 主要得到了以下 一些结果: 对于一个连通的、度k大于2且围长g大于5的点传递图G, 我们证明了, 如果k=3且g≥7, 那么对于任何一个小于等于g且不等于g-1或g-2的正整数s, G都是超\lambda_{s}的; 如果k=4且g>5, 那么对于任何一个小于等于g且不等于g-1的正整数s, G都是超\lambda_{s}的; 如果k>4且g>5, 那么对于任何一个小于等于g的正整数s, G都是超\lambda_{s}的; ...
Other AbstractOne work in this PhD thesis is to study the p-factor-criticality of vertex-transitive graphs. The concept of p-factor-critical graphs was proposed by Favaron and Yu, independently. A graph of order n is p-factor-critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1-Factor-critical graphs and 2-factor-critical graphs are factor-critical graphs and bicritical graphs, respectively. It was showed in the monograph Matching Theory written by Lovasz and Plummer that every connected vertex-transitive graph of odd order is factor-critical and every connected non-bipartite vertex-transitive graph of even order is bicritical. We consider further the p-factor-criticality of vertex-transitive graphs for p=3,4. Firstly, we give a characterization of the 3-factor-criticality of vertex-transitive graphs. We proved that a connected vertex-transitive graph of odd order n≥3 either is a cycle or is 3-factor-critical. This general result is stronger than Miklavic and Sparl's, who showed that a connected Cayley graph on an abelian group of odd order n≥3 either is a cycle or is 1.5-extendable. We also characterize the 4-factor-criticality of vertex-transitive graphs. we prove that a connected non-biaprtite vertex-transitive k-regular graph G of even order at least $6$ is 4-factor-critical if and only if k≥5. It follows by this result that a connected non-bipartite Cayley graph of even order and degree larger than 4 is 2-extendable. This solves partly the open problem of characterizing 2-extendable Cayley graphs, raised by Chan, Chen and Yu. In the study of the p-factor-criticality of vertex-transitive graphs, we make an application of many results about the s-restricted edge-connectivity of vertex-transitive graphs. In order to study the larger p-factor-criticality of vertex-transitive graphs, we do a special study on the s-restricted edge-connectivity of vertex-transitive graph in this PhD thesis. The concept of s-restricted edge-connectivity of graphs, proposed by Fabrega and Fiol, can be used to analyze the reliability of networks better. For a connected graph G and some positive integer s, an edge-cut F of G is said to be an s-restricted edge-cut of G if every component of G-F has at least s vertices. The minimum cardinality of s-restricted edge-cuts of G is the s-restricted edge-connectivity of G, denoted by \lambda_{s}(G). Let \xi_{s}(G) = min{d(X):X\subseteq V(G) such that |...
URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225520
Collection数学与统计学院
Recommended Citation
GB/T 7714
孙午阳. 点传递图的p因子临界性与s限制边连通性[D]. 兰州. 兰州大学,2014.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[孙午阳]'s Articles
Baidu academic
Similar articles in Baidu academic
[孙午阳]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[孙午阳]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.