共查询到20条相似文献,搜索用时 31 毫秒
1.
Best upper and lower bounds, as functions of n, are obtained for the quantities and , where β2(G) denotes the total matching number and α2(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α2(G)+β2(G), when G is a connected graph. 相似文献
2.
Tom Brylawski 《Discrete Mathematics》1977,18(3):243-252
In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if X(G) = Σμ(0, x)λr ? r(x) = Σ (?1)r ? kWkλk is the characteristic polynomial of G, then Thus γ(G) ? 2r ? 1 (n+2), where γ(G) = Σwk. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then |μ| ? (r? 1)n; and γ ? (2r ? 1 ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, , and then . Further, if β is the Crapo invariant, then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network. 相似文献
3.
Cai Mao-cheng 《Discrete Mathematics》1982,41(3):229-234
Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) ; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph Kk,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove and characterize all minimally k-connected graphs of order n and size . 相似文献
4.
Jerrold R Griggs 《Journal of Combinatorial Theory, Series B》1983,34(1):22-39
Wei discovered that the independence number of a graph G is at least Σv(1 + d(v))?1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 vertices and if G is neither an odd cycle nor an odd path, then the bound above can be increased by , where Δ is the maximum degree. This new bound is sharp for even cycles and for three other graphs. These results relate nicely to some algorithms for finding large independent sets. They also have a natural matrix theory interpretation. A survey of other known lower bounds on the independence number is presented. 相似文献
5.
Colin McDiarmid 《Discrete Applied Mathematics》1983,5(1):123-132
When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ fχ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs Gn,p with n vertices, fχ(Gn,p) is almost surely at least (?ε)n, despite say the fact that the largest complete subgraph of Gn,p has only about log n vertices. 相似文献
6.
Alan L.T Paterson 《Journal of Functional Analysis》1983,53(3):203-223
A theory of harmonic analysis on a metric group (G, d) is developed with the model of U, the unitary group of a C1-algebra , in mind. Essential in this development is the set of contractive, irreducible representations of G, and its concomitant set Pd(G) of positive-definite functions. It is shown that is compact and closed in . The set is determined in a number of cases, in particular when G = U() with abelian. If is an AW1-algebra, it is shown that d is essentially the same as . Unitary groups are characterised in terms of a certain Lie algebra u and several characterisations of G = U() when is abelian are given. 相似文献
7.
Joel M Cohen 《Journal of Functional Analysis》1982,48(3):301-309
Let G be a group and g1,…, gt a set of generators. There are approximately (2t ? 1)n reduced words in g1,…, gt, of length ?n. Let be the number of those which represent 1G. We show that exists. Clearly 1 ? γ ? 2t ? 1. is the cogrowth. 0 ? η ? 1. In fact . The entropic dimension of G is shown to be 1 ? η. It is then proved that d(G) = 1 if and only if G is free on g1,…, gt and d(G) = 0 if and only if G is amenable. 相似文献
8.
Henry A Kierstead 《Journal of Combinatorial Theory, Series B》1984,36(2):156-160
Let M be a multigraph. Vizing (Kibernetika (Kiev)1 (1965), 29–39) proved that χ′(M)≤Δ(M)+μ(M). Here it is proved that if χ′(M)≥Δ(M)+s, where then M contains a 2s-sided triangle. In particular, (C′) if μ(M)≤2 and M does not contain a 4-sided triangle then χ′(M)≤Δ(M) + 1. Javedekar (J. Graph Theory4 (1980), 265–268) had conjectured that (C) if G is a simple graph that does not induce K1,3 or K5?e then χ(G)≤ω(G) + 1. The author and Schmerl (Discrete Math.45 (1983), 277–285) proved that (C′) implies (C); thus Javedekar's conjecture is true. 相似文献
9.
Peter J. Slater 《Discrete Mathematics》1981,34(2):185-193
The concept of a k-sequential graph is presented as follows. A graph G with ∣V(G)∪ E(G)∣=t is called k-sequential if there is a bijection such that for each edgein E(G) one has. A graph that is 1-sequential is called simply sequential, and, in particular the author has conjectured that all trees are simply sequential. In this paper an introductory study of k-sequential graphs is made. Further, several variations on the problems of gracefully or sequentially numbering the elements of a graph are discussed. 相似文献
10.
For a permutation σ of the integers from 1 to n, let ?(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let ?(n) be the largest such ?(σ) for all σ in (the symmetric group) Sn. We show that , and that for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey . 相似文献
11.
12.
Let G be a finite group having a faithful irreducible character χ for which χ(1) is prime to ¦G¦/χ(1). Let n=[(χ):]χ(1), and assume that the factors are not both even. Then G can be embedded in GLn() in such a way that its normalizer therein splits over its centralizer. 相似文献
13.
The initial and boundary value problem for the degenerate parabolic equation vt = Δ(?(v)) + F(v) in the cylinder bounded, for a certain class of point functions ? satisfying ?′(v) ? 0 (e.g., ) is considered. In the case that F(v) sign , the equation has a global time solution. The same is true for α = 1 provided the measure of Ω is sufficiently small. In the case that is nondecreasing a condition is given on the initial state v(x, 0) which implies that the solution must blow up in finite time. The existence of such initial states is discussed. 相似文献
14.
15.
Frances Chevarley Edmonds 《Discrete Mathematics》1977,19(3):213-227
In this paper we studied m×n arrays with row sums and column sums where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function Hm,n(r), which enumerates m×n arrays with row sums and column sums and respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function Gm,n(y) = Σr?0Hm,n(r)yr, it was found to be rational of degree less than zero. The denominator of Gm,n(y) is of the form (1?y)(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation. 相似文献
16.
A lower (upper) bound is given for the distribution of each dj, j = k + 1, …, p (j = 1, …, s), the jth latent root of AB?1, where A and B are independent noncentral and central Wishart matrices having with rank and Wp(n, Σ), respectively. Similar bound are also given for the distributions of noncentral means and canonical correlations. The results are applied to obtain lower bounds for the null distributions of some multivariate test statistics in Tintner's model, MANOVA and canonical analysis. 相似文献
17.
Vladimir V Peller 《Journal of Functional Analysis》1983,53(1):74-83
Some continuity properties of the averaging projection onto the set of Hankel matrices are investigated. It is proved that this projection is of weak type (1, 1) which means that for any nuclear operator T the s-numbers of T satisfy Sn(T) ? const(n + 1). As a consequence it is obtained that maps the Matsaev ideal ω = {T:∑n?0Sn(T)(2n + 1)?1 < ∞} into the set of compact operators. 相似文献
18.
A t-spread set [1] is a set of (t + 1) × (t + 1) matrices over GF(q) such that ∥C∥ = qt+1, 0 ? C, I?C, and det(X ? Y) ≠ 0 if X and Y are distinct elements of . The amount of computation involved in constructing t-spread sets is considerable, and the following construction technique reduces somewhat this computation. Construction: Let be a subgroup of GL(t + 1, q), (the non-singular (t + 1) × (t + 1) matrices over GF(q)), such that ∥G∥|at+1, and det (G ? H) ≠ 0 if G and H are distinct elements of . Let A1, A2, …, An?GL(t + 1, q) such that det(Ai ? G) ≠ 0 for i = 1, …, n and all G?G, and det(Ai ? AjG) ≠ 0 for i > j and all G?G. Let , and ∥C∥ = qt+1. Then is a t-spread set. A t-spread set can be used to define a left V ? W system over V(t + 1, q) as follows: x + y is the vector sum; let e?V(t + 1, q), then xoy = yM(x) where M(x) is the unique element of with x = eM(x). Theorem: Letbe a t-spread set and F the associatedV ? Wsystem; the left nucleus = {y | CM(y) = C}, and the middle nucleus = }y | M(y)C = C}. Theorem: Forconstructed as aboveG ? {M(x) | x?Nλ}. This construction technique has been applied to construct a V ? W system of order 25 with ∥Nλ∥ = 6, and ∥Nμ∥ = 4. This system coordinatizes a new projective plane. 相似文献
19.
Béla Bollobás 《Discrete Mathematics》1979,28(3):321-323
The note contains some conditions on a graph implying that the edge connectivity is equal to the minimum degree. One of these conditions is that if d1?d2???dn is the degree sequence then ∑ll?1(d1+dn?1)>In?1 for . 相似文献
20.
David M. Mason 《Stochastic Processes and their Applications》1983,15(1):99-109
Let Gn denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between Gn(u) and u of the forms 6wv(u)Dn(u)6 and 6wv(Gn(u))Dn(u)6, where Dn(u) = Gn(u)?u, wv(u) = (u(1?u))?1+v and 0 ? v < is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function wv with ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function wv with 0 ? v < are potentially applicable in the construction of confidence contours for the extreme tails of a distribution. 相似文献