排序方式: 共有4条查询结果,搜索用时 0 毫秒
1
1.
We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular
bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings Mk exist with |Mk∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k. 相似文献
2.
F. Pakovich 《Bulletin des Sciences Mathématiques》2005,129(9):749-774
In this paper we investigate the following “polynomial moment problem”: for a given complex polynomial P(z) and distinct a,b∈C to describe polynomials q(z) orthogonal to all powers of P(z) on [a,b]. We show that for given P(z), q(z) the condition that q(z) is orthogonal to all powers of P(z) is equivalent to the condition that branches of the algebraic function Q(P−1(z)), where , satisfy a certain system of linear equations over Z. On this base we provide the solution of the polynomial moment problem for wide classes of polynomials. In particular, we give the complete solution for polynomials of degree less than 10. 相似文献
3.
We report some properties of the reciprocal molecular topological index RMTI of a connected graph, and, in particular, its
relationship with the first Zagreb index M1. We also derive the upper bounds for RMTI in terms of the number of vertices and the number of edges for various classes
of graphs, including K
r+1 -free graphs with r ≥ 2, quadrangle-free graphs, and cacti. Additionally, we consider a Nordhaus-Gaddum-type result for RMTI. 相似文献
4.
Summary The pruning method developed earlier by one of the authors (K.B.) combined with the operator method is shown to yield powerful recursive relations for generating functions for dimer statistics and characteristic polynomials of cacti graphs and cacti lattices. The method developed is applied to linear cacti, Bethe cacti of any length containing rings of any size, and cyclic cacti of any length and size. It is shown that exact dimer statistics can be done on any cactus lattice.Dedicated to Professor V. Krishnamurthy on the occasion of his 60th birthdayAlfred P. Sloan fellow; Camille and Henry Dreyfus teacher-scholar 相似文献
1