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...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.展开更多
文摘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.
