Threshold Functions for Factor-critical Graphs
Threshold Functions for Factor-critical Graphs
摘要
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 Qf 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.
参考文献13
-
1BARBOUR A D, HOLST L, JANSON S. Poisson Approximation[M]. University of Michigan: Oxford Uni?versity Press, 1992.
-
2BOLLOBAs B. The Evoltion of Sparse Graphs, Graph Theory and Combinatorics[C]. Cambridge: Aca?demic Press, 1984: 35-37.
-
3BOLLOBAs B, FENNER T I, FRIEZE A M. Hamilton cycles in random graphs of minimal degree at least k[C]. A tribute to Paul Erdos, Cambridge Univ Press, 1990: 59-95.
-
4BOLLOBAs B, FRIEZE A M. On Matchings and Hamilton Cycles in Random Graphs, Random Graphs '83(Poznan, 1983)[C]. Narth-Holland: Amsterdam, 1985: 23-46.
-
5BOOLOHAs B, THOMASON A. Random Graphs of Small Order, Random Graphs '83(Poznan, 1983)[C]. Amsterdam: Narth-Holland, 1985: 47-97.
-
6ERDOS P, RENYI A. On random matrices[J]. Publ Math Inst Hungar Acad Sci, 1964, 8: 455-46l.
-
7ERDOS P, RENYI A. On the existence of a factor of degree one of a connected random graph[J]. Acta Math Acad Sci Hungar, 1966, 17: 359-368.
-
8IVCHENKO G 1. The strength of connectivity of a random graph[J]. Theory Probab Applies, 1973, 18: 188-195.
-
9JANSON S, LUCZAK T, RUCINSKI A. Random Graphs[M]. New York John Wiley and Sons, Inc, 2000.
-
10LUCZAK T. On matchings and Hamiltnian cycles in subgraphs of random graphs, Random graphs '85+(Poznan, 1985)[C]. Narth-Hollamd: 'Amsterdam, 1985: 171-185.
-
1Jianxiang LI,Yinghong MA.DEGREE CONDITIONS FOR GRAPHS TO BE FRACTIONAL(a,b,n)-CRITICAL GRAPHS[J].Journal of Systems Science & Complexity,2006,19(4):491-497.
-
2段广森,王新社.Hamilton Properties of Domination Critical Graphs[J].Chinese Quarterly Journal of Mathematics,1998,13(1):14-21.
-
3Si Zhong ZHOU,Zhi Ren SUN.On All Fractional(a,b,k)-Critical Graphs[J].Acta Mathematica Sinica,English Series,2014,30(4):696-702. 被引量：2
-
4LIU Guizhen and WANG Jianfang Department of Mathematics, Shandong University, Jinan 250100, China,Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing 100080, China.(a, b, k )-critical graphs[J].Chinese Science Bulletin,1997,42(17):1492-1493.
-
5Si Zhong ZHOU.Binding Numbers for Fractional ID-k-factor-critical Graphs[J].Acta Mathematica Sinica,English Series,2014,30(1):181-186.
-
6王莹,侯新民.连通控制临界图的双因子临界性[J].数学学报（中文版）,2012,55(6):1033-1038.
-
7GaiGuanghong QuLiangsheng.TRANSLATION-INVARIANT BASED ADAPTIVE THRESHOLD DENOISING FOR IMPACT SIGNAL[J].Chinese Journal of Mechanical Engineering,2004,17(4):552-555. 被引量：4
