Factor-critical 图的阈值

数学季刊 ›› 2013, Vol. 28 ›› Issue (3): 417-427.

Factor-critical 图的阈值

1. Public Department, Suzhou Industrial Park Institute of Services Outsourcing 2. School of Mathematics and Statistics, Xi'an Jiaotong University 3. Department of Mathematics and Statistics, Thompson Rivers University

收稿日期:2012-06-12 出版日期:2013-09-30 发布日期:2023-02-24
作者简介:HUAN Xiao(1982-), female, native of Xinyi, Jiangsu, a lecturer of Suzhou Industrial Park Institute of Services Outsourcing, Ph.D., engages in graph theory and its applications; LU Hong-liang(1981-), male, native of Kaifeng, Henan, a lecturer of Xi’an Jiaotong University, Ph.D., engages in graph theory and its applications; YU Qing-lin(1962-), male, native of Kamloops BC, Canada, a professor of Thompson Rivers University, engages in graph theory and its applications.
基金资助:
Supported by the Natural Sciences and Engineering Research Council of Canada(OGPO122059)

Threshold Functions for Factor-critical Graphs

1. Public Department, Suzhou Industrial Park Institute of Services Outsourcing 2. School of Mathematics and Statistics, Xi'an Jiaotong University 3. Department of Mathematics and Statistics, Thompson Rivers University

Received:2012-06-12 Online:2013-09-30 Published:2023-02-24
About author:HUAN Xiao(1982-), female, native of Xinyi, Jiangsu, a lecturer of Suzhou Industrial Park Institute of Services Outsourcing, Ph.D., engages in graph theory and its applications; LU Hong-liang(1981-), male, native of Kaifeng, Henan, a lecturer of Xi’an Jiaotong University, Ph.D., engages in graph theory and its applications; YU Qing-lin(1962-), male, native of Kamloops BC, Canada, a professor of Thompson Rivers University, engages in graph theory and its applications.
Supported by:
Supported by the Natural Sciences and Engineering Research Council of Canada(OGPO122059)

摘要/Abstract

摘要： A connected graph G is said to be k-extendable if it has a set of k independent edges and each set of k independent edges in G can be extended to a perfect matching of G. A graph G is k-factor-critical if G-S has a perfect matching for any k-subset S of V(G). The basic properties of k-extendable and k-factor-critical graphs have been investigated in [11] and [13]. In this paper, we determine thresholds for k-factor-critical graphs and k-extendable bipartite graphs. For non-bipartite k-extendable graphs, we find a probability sequence, which acts the same way like a threshold.

关键词: k-extendable, k-factor-critical, threshold

Abstract: A connected graph G is said to be k-extendable if it has a set of k independent edges and each set of k independent edges in G can be extended to a perfect matching of G. A graph G is k-factor-critical if G-S has a perfect matching for any k-subset S of V(G). The basic properties of k-extendable and k-factor-critical graphs have been investigated in [11] and [13]. In this paper, we determine thresholds for k-factor-critical graphs and k-extendable bipartite graphs. For non-bipartite k-extendable graphs, we find a probability sequence, which acts the same way like a threshold.

Key words: k-extendable, k-factor-critical, threshold

中图分类号:

O157.5

郇潇, 鲁红亮, 于青林. Factor-critical 图的阈值[J]. 数学季刊, 2013, 28(3): 417-427.

HUAN Xiao, LU Hong-liang, YU Qing-lin. Threshold Functions for Factor-critical Graphs[J]. Chinese Quarterly Journal of Mathematics, 2013, 28(3): 417-427.

[1]	高建忠, 张太雷. 一类具有脉冲接种、双时滞的SEIRS传染病模型研究分析[J]. 数学季刊, 2019, 34(1): 75-87.
[2]	韩金广, 亢保元. 门限代理门限签名方案的密码学分析[J]. 数学季刊, 2010, 25(3): 459-463.
[3]	郭红建, 赵中, 宋新宇等. 一类带有HollingⅡ类功能性反应和相互干扰及脉冲效应的捕食系统[J]. 数学季刊, 2008, 23(4): 480-490.