共查询到20条相似文献,搜索用时 125 毫秒
1.
几类图的匹配等价图类 总被引:1,自引:0,他引:1
魏岭 《数学的实践与认识》2011,41(17)
两个图G和H的匹配多项式相等,则称它们匹配等价.用[G]表示图G的所有不同构的匹配等价图的集合.刻画了匹配次大根小于1的图及这些图的补图的匹配等价图类. 相似文献
3.
4.
本文研究了具有度序列(13,2S-4,3)的图的匹配唯一性,给出了T(1,4,n)∪(s∪i=0Cpi)(n 4)与T(1,5,n)∪(s∪i=0Cpi)(n 5)及其补图匹配唯一的充要条件. 相似文献
5.
6.
几类图的匹配多项式之间的关系与一类图的匹配等价图 总被引:1,自引:0,他引:1
张海良 《纯粹数学与应用数学》2007,23(2):178-182
研究了几类图的匹配多项式以及它们之间的一些整除关系,给出了路的匹配多项式相互整除的一个充分必要条件,并且刻画了图T2,2,n的所有匹配等价图. 相似文献
7.
8.
9.
利用图的匹配多项式及其最大实数根的性质证明了树T(1,1,n,2,1)及补图匹配唯一的充要条件是n≠1,2,5,8. 相似文献
10.
11.
Leon Pesotchinsky 《Statistics & probability letters》1984,2(5):305-310
A discrete time process on [0,1] considered in this paper is related to various problems involving two independent samples. In particular one may suggest a simple matching rule for the case of continuously generated samples and a goodness-of-fit test based on the number of unmatched elements. A recurrence formula for computing the exact distribution of this statistic and the asymptotic behavior of its expectation are found. 相似文献
12.
申世昌 《纯粹数学与应用数学》2008,24(1):107-110
讨论简单无向图G的匹配唯一性,研究T形树T(m,n,s)匹配唯一的充分条件.利用匹配多项式根的信息,根据其定义以及图的度序列和匹配多项式的性质推导.若T形树T(m,n,s)是几乎等长的,则其是匹配唯一的.找到了T形树T(m,n,s)匹配唯一的一个充分条件,并得到了图的匹配多项式根的一些性质. 相似文献
13.
In this note, we determine the maximum number of edges of a k-uniform hypergraph, k≥3, with a unique perfect matching. This settles a conjecture proposed by Snevily. 相似文献
14.
A graph G is a {d, d+k}-graph, if one vertex has degree d+k and the remaining vertices of G have degree d. In the special case of k = 0, the graph G is d-regular. Let k, p ⩾ 0 and d, n ⩾ 1 be integers such that n and p are of the same parity. If G is a connected {d, d+k{-graph of order n without a matching M of size 2|M| = n − p, then we show in this paper the following: If d = 2, then k ⩾ 2(p + 2) and
If d ⩾ 3 is odd and t an integer with 1 ⩽ t ⩽ p + 2, then
If d ⩾ 4 is even, then
The special case k = p = 0 of this result was done by Wallis [6] in 1981, and the case p = 0 was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible. 相似文献
(i) | n ⩾ k + p + 6. |
(ii) | n ⩾ d + k + 1 for k ⩾ d(p + 2) |
(iii) | n ⩾ d(p + 3) + 2t + 1 for d(p + 2 −t) + t ⩽ k ⩽ d(p + 3 −t) + t − 3 |
(iv) | n ⩾ d(p + 3) + 2p + 7 for k ⩽ p. |
(v) | n ⩾ d + k + 2 − η for k ⩾ d(p + 3) + p + 4 + η |
(vi) | n ⩾ d + k + p + 2 − 2t = d(p + 4) + p + 6 for k = d(p + 3) + 4 + 2t and p ⩾ 1 |
(vii) | n ⩾ d + k + p + 4 for d(p + 2) ⩽ k ⩽ d(p + 3) + 2 |
(viii) | n ⩾ d(p + 3) + p + 4 for k ⩽ d(p + 2) − 2, where 0 ⩽ t ⩽ 1/2p − 1 and η = 0 for even p and 0 ⩽ t ⩽ 1/2(p − 1) and η = 1 for odd p. |
15.
A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and . 相似文献
16.
17.
In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d−1 for MIM in d-regular graphs, for each d3. We also prove that MIM is APX-complete in d-regular graphs, for each d3. 相似文献
18.
V. Papathanasiou 《Annals of the Institute of Statistical Mathematics》1995,47(1):171-176
A new derivation of the classical orthogonal polynomials is given by using thew-function which appears in the variance bounds and some properties of the Pearson system of distributions. Also a characterization of the Pearson system of distributions through some conditional moments is obtained by using a result obtained by Johnson (1993) concerning this family. 相似文献
19.
Xiaoyan Jiang Heping Zhang 《Discrete Applied Mathematics》2011,159(15):1581-1593
Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two. 相似文献
20.