位置:成果数据库 > 期刊 > 期刊详情页
匹配覆盖图的阈函数
  • ISSN号:1005-3085
  • 期刊名称:《工程数学学报》
  • 时间:0
  • 分类:O157.5[理学—数学;理学—基础数学]
  • 作者机构:[1]苏州工业园区服务外包职业学院金融系,苏州215123, [2]西安交通大学数学与统计学院,西安710049, [3]汤普森河大学数学与统计系,加拿大
  • 相关基金:The National Natural Science Foundation of China (11101329); the Natural Sciences and Engineering Research Council of Canada (OGP0122059).
中文摘要:

一个图G是匹配覆盖的(或1-可扩的)如果它是连通的且G的每条边都被包含在一个完美匹配里。我们称一个图G为双因子临界的,如果对于G中的任意两个不同顶点x, y,G-x-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.

同期刊论文项目
同项目期刊论文
期刊信息
  • 《工程数学学报》
  • 北大核心期刊(2011版)
  • 主管单位:教育部
  • 主办单位:西安交通大学
  • 主编:李大潜
  • 地址:西宁市咸宁西路28号西安交通大学数学与统计学院
  • 邮编:710049
  • 邮箱:jgsx@mail.xjtu.edu.cn
  • 电话:029-82667877
  • 国际标准刊号:ISSN:1005-3085
  • 国内统一刊号:ISSN:61-1269/O1
  • 邮发代号:
  • 获奖情况:
  • 《中文核心期刊要目总览》核心期刊,《中国科学引文数据库》核心期刊,《中国数学文摘》核心期刊,陕西省优秀科技期刊
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国数学评论(网络版),德国数学文摘,荷兰文摘与引文数据库,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版),中国北大核心期刊(2000版)
  • 被引量:6741