摘要
一个图G是匹配覆盖的(或1-可扩的)如果它是连通的且G的每条边都被包含在一个完美匹配里.我们称一个图G为双因子临界的,如果对于G中的任意两个不同顶点x,y,Gx-y都有一个完美匹配.一个双因子临界图被称为砖块,如果它是3-连通的.本文对于双因子临界图与匹配覆盖二部图确定了它们的阈函数.对于非二部的匹配覆盖图,我们发现了一个概率序列,其表现就像一个阈.此外,我们证明几乎所有的3-连通图均是砖块.
A graph G is matching-covered (or 1-extendable) if it is connected and every edge of G is contained in a perfect matching. We call a graph G bicritical if G-x-y has a perfect matching for every pair of distinct vertices x and y in G. A bicritical graph is called a brick if it is 3-connected. In this paper, we determine thresholds for bicritical graphs and matching-covered bipartite graphs. For non-bipartite matching-covered graphs, we find a probability sequence which acts the same way like a threshold. Furthermore, we show that asymptotically almost surely all 3-connected graphs are bricks.
出处
《工程数学学报》
CSCD
北大核心
2014年第4期622-632,共11页
Chinese Journal of Engineering Mathematics
基金
The National Natural Science Foundation of China(11101329)
the Natural Sciences and Engineering Research Council of Canada(OGP0122059)
关键词
匹配覆盖
砖
2-因子临界性
阈
负相关
matching-covered
brick
bicriticality
threshold
negatively related