共查询到20条相似文献,搜索用时 31 毫秒
1.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
2.
Sylvie Corteel Ira M. Gessel Carla D. Savage Herbert S. Wilf 《Annals of Combinatorics》2007,11(3-4):375-386
We compute the joint distribution of descent and major index over permutations of {1,..., n} with no descents in positions {n − i, n − i + 1, ... , n − 1} for fixed i ≥ 0. This was motivated by the problem of enumerating symmetrically constrained compositions and generalizes Carlitz’s q-Eulerian polynomial.
Received December 19, 2006 相似文献
3.
Roy Meshulam 《Graphs and Combinatorics》1992,8(3):287-289
Let ℱ be a family ofn−k-dimensional faces of the discrete cube {0,1}
n
such that for allF ε ℱ, F ⊄ ∪ { F′: F ≠ F′ ∈ ℱ}. It is shown that ifn≥n
0
(k) then |ℱ| ≤
. This was conjectured by Aharoni and Holzman and is the casem=2 of a more general result on faces of {0,...,m−1}n. 相似文献
4.
A {1, 3, …,2n ? 1}-factor of a graph G is defined to be a spanning subgraph of G, each degree of whose vertices is one of {1, 3, …, 2n ? 1}, where n is a positive integer. In this paper, we give a sufficient condition for a graph to have a {1, 3, …, 2n ? 1}-factor. 相似文献
5.
In this paper, the sharp estimates of all homogeneous expansions for f are established, where f(z) = (f
1(z), f
2(z), …, f
n
(z))′ is a k-fold symmetric quasi-convex mapping defined on the unit polydisk in ℂ
n
and
$
\begin{gathered}
\frac{{D^{tk + 1} + f_p \left( 0 \right)\left( {z^{tk + 1} } \right)}}
{{\left( {tk + 1} \right)!}} = \sum\limits_{l_1 ,l_2 ,...,l_{tk + 1} = 1}^n {\left| {apl_1 l_2 ...l_{tk + 1} } \right|e^{i\tfrac{{\theta pl_1 + \theta pl_2 + ... + \theta pl_{tk + 1} }}
{{tk + 1}}} zl_1 zl_2 ...zl_{tk + 1} ,} \hfill \\
p = 1,2,...,n. \hfill \\
\end{gathered}
$
\begin{gathered}
\frac{{D^{tk + 1} + f_p \left( 0 \right)\left( {z^{tk + 1} } \right)}}
{{\left( {tk + 1} \right)!}} = \sum\limits_{l_1 ,l_2 ,...,l_{tk + 1} = 1}^n {\left| {apl_1 l_2 ...l_{tk + 1} } \right|e^{i\tfrac{{\theta pl_1 + \theta pl_2 + ... + \theta pl_{tk + 1} }}
{{tk + 1}}} zl_1 zl_2 ...zl_{tk + 1} ,} \hfill \\
p = 1,2,...,n. \hfill \\
\end{gathered}
相似文献
6.
Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the
following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we
cannot replace δ − 1 by δ, respectively. 相似文献
7.
Sergey Bereg 《Graphs and Combinatorics》2009,25(2):139-144
We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning
trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning
trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G.
A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph
G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice. 相似文献
8.
A. V. Stolyarov 《Journal of Mathematical Sciences》2011,177(5):716-724
In this paper, we study the internal geometry of a hypersurface V
n−1 embedded in a projectively metric space K
n
, n ≥ 3, and equipped with fields of geometric-objects { Gni,Gi } \left\{ {G_n^i,{G_i}} \right\} and { Hni,Gi } \left\{ {H_n^i,{G_i}} \right\} in the sense of Norden and with a field of a geometric object { Hni,Hn } \left\{ {H_n^i,{H_n}} \right\} in the sense of Cartan. For example, we have proved that the projective-connection space P
n−1,n−1 induced by the equipment of the hypersurface Vn - 1 ì Kn, n 3 3 {V_{n - 1}}\; \subset \;{K_n},\;n \geq 3 , in the sense of Cartan with the field of a geometrical object { Hni,Hn } \left\{ {H_n^i,{H_n}} \right\} is flat if and only if its normalization by the field of the object { Hni,Gi } \left\{ {H_n^i,{G_i}} \right\} in the tangent bundle induces a Riemannian space R
n−1 of constant curvature K = −1/c. 相似文献
9.
Daniel Wulbert 《Israel Journal of Mathematics》2001,126(1):363-380
LetX be a Borel subset of a separable Banach spaceE. Letμ be a non-atomic,σ-finite, Borel measure onX. LetG ⊆L
1 (X, Σ,μ) bem-dimensional.
Theorem:There is an l ∈ E* and real numbers −∞=x
0<x
1<x
2<…<x
n<x
n+1=∞with n≤m, such that for all g ∈ G,
相似文献
10.
Giovanni Sansone 《Annali di Matematica Pura ed Applicata》1926,3(1):73-107
Sommario Introduzione — § 1 – 1. L'indice μ(n) dei sottogruppi Гμ(n) del gruppo Γ di sostituzioni lineari unimodulari con coefficienti del campo diJacobi-Eisenstein
— 2. Il poliedro fondamentale del sottogruppo Гμ(1−ε) — § 2 – 3. I campi fondamentali dei gruppi Гμ(n) — 4. Impossibilità di limitare con un numero finito di piani e sfere di riflessione i poliedri fondamentali dei gruppi Гμ(n), conn intero razionale pari, diverso da 2 — § 3 – 5. Relazioni fondamentali fra le sostituzioni generatrici del gruppo
di sostituzioni lineari con coefficienti del corpo Kε con determinante ±1 — § 4 – 6. Sulla indipendenza delle sostituzioniS,T,U, generatrici del gruppo finito G2μ(n) e sulle loro relazioni caratteristiche nel gruppo G2μ(n) — § 5 – 7. Dimostrazione del teorema fondamentale sui gruppi G2μ(n). Lemmi preliminari — 8, Dimostrazione del teorema fondamentale nel caso di moduli primi con 2(1−ε) — § 6 – 9. Il teorema
fondamentale per i modulim(1−ε), 3m, 2m, 2m(1−ε), 6m conm primo con 6 – 10. Immagine geometrica dei gruppi G2μ(1−ε) — § 7 – 11. Il gruppo delle sostituzioni unimodulari
, [c/1+4ma]=+1, e il caso eccezionale dei moduli 4m – 12. Il gruppo delle sostituzioni unimodulari
[c/1+3m(1−ε)a]3=+1 e il caso eccezionale dei moduli 3(1−ε)m. 相似文献
11.
Thomas Westerbäck 《Designs, Codes and Cryptography》2007,42(3):335-355
A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of .
A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This
condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that
the packing number p, for any maximal strictly partial Hamming packing of , n = 2
m
−1, satisfies .
It is also proved that for any n equal to 2
m
−1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2
m
−1, .
All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.
相似文献
12.
V. F. Molchanov 《Acta Appl Math》2007,99(3):321-337
We define canonical representations R
λ
,
, for the Lobachevsky space ℒ=G/K of dimension n−1 where G=SO0(n−1,1), K=SO(n−1), as the restriction to G of maximal degenerate series representations of the overgroup
. We determine explicitly the interaction of Lie operators of
with operators intertwining canonical representations and representations of G associated with a cone.
Supported by the Russian Foundation for Basic Research: grants No. 05-01-00074a and No. 05-01-00001a, the Netherlands Organization
for Scientific Research (NWO): grant 047-017-015, the Scientific Program “Devel. Sci. Potent. High. School”: project RNP.2.1.1.351
and Templan No. 1.2.02. 相似文献
13.
Let Δn−1 denote the (n − 1)-dimensional simplex. Let Y be a random 2-dimensional subcomplex of Δn−1 obtained by starting with the full 1-dimensional skeleton of Δn−1 and then adding each 2−simplex independently with probability p. Let
denote the first homology group of Y with mod 2 coefficients. It is shown that for any function ω(n) that tends to infinity
14.
Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible. 相似文献
15.
Henry Teicher 《Journal of Theoretical Probability》1995,8(4):779-793
Conditions are obtained for (*)E|S
T
|γ<∞, γ>2 whereT is a stopping time and {S
n=∑
1
n
,X
j
ℱ
n
,n⩾1} is a martingale and these ensure when (**)X
n
,n≥1 are independent, mean zero random variables that (*) holds wheneverET
γ/2<∞, sup
n≥1
E|X
n
|γ<∞. This, in turn, is applied to obtain conditions for the validity ofE|S
k,T
|γ<∞ and of the second moment equationES
k,T
2
=σ
2
EΣ
j=k
T
S
k−1,j−1
2
where
and {X
n
, n≥1} satisfies (**) and
,n≥1. The latter is utilized to elicit information about a moment of a stopping rule. It is also shown for i.i.d. {X
n
, n≥1} withEX=0,EX
2=1 that the a.s. limit set of {(n log logn)−k/2
S
k,n
,n≥k} is [0,2
k/2/k!] or [−2
k/2/k!] according ask is even or odd and this can readily be reformulated in terms of the corresponding (degenerate kernel)U-statistic
. 相似文献
16.
Alexander A. Razborov 《Proceedings of the Steklov Institute of Mathematics》2011,274(1):247-266
Fon-Der-Flaass (1988) presented a general construction that converts an arbitrary [(C)\vec]4\vec C_4 -free oriented graph Γ into a Turán (3, 4)-graph. He observed that all Turán-Brown-Kostochka examples result from his construction,
and proved the lower bound $\tfrac{4}
{9}
$\tfrac{4}
{9}
(1 − o(1)) on the edge density of any Turán (3, 4)-graph obtainable in this way. In this paper we establish the optimal bound $\tfrac{3}
{7}
$\tfrac{3}
{7}
(1 − o(1)) on the edge density of any Turán (3, 4)-graph resulting from the Fon-Der-Flaass construction under any of the following
assumptions on the undirected graph G underlying the oriented graph Γ: (i) G is complete multipartite; (ii) the edge density of G is not less than $\tfrac{2}
{3} - \varepsilon $\tfrac{2}
{3} - \varepsilon for some absolute constant ε > 0. We are also able to improve Fon-Der-Flaass’s bound to $\tfrac{7}
{{16}}
$\tfrac{7}
{{16}}
(1 − o(1)) without any extra assumptions on Γ. 相似文献
17.
Let dα be a measure on R and let σ = (m
1, m
2,...,m
n
), where m
k
≥ 1, k = 1,2,...,n, are arbitrary real numbers. A polynomial ω
n
(x) := (x − x
1)(x − x
2)...(x − x
n
) with x
1 ≤ x
2 ≤ ... ≤ x
n
is said to be the nth σ-orthogonal polynomial with respect to dα if the vector of zeros (x
1, x
2, ..., x
n)T is a solution of the extremal problem
18.
Nariaki Sugiura 《Annals of the Institute of Statistical Mathematics》1974,26(1):117-125
Summary LetS
i have the Wishart distributionW
p(∑i,ni) fori=1,2. An asymptotic expansion of the distribution of
for large n=n1+n2 is derived, when∑
1∑
2
−1
=I+n−1/2θ, based on an asymptotic solution of the system of partial differential equations for the hypergeometric function2
F
1, obtained recently by Muirhead [2]. Another asymptotic formula is also applied to the distributions of −2 log λ and −log|S
2(S
1+S
2)−1| under fixed∑
1∑
2
−1
, which gives the earlier results by Nagao [4]. Some useful asymptotic formulas for1
F
1 were investigated by Sugiura [7]. 相似文献
19.
N. I. Osetinskii 《Computational Mathematics and Modeling》2010,21(4):391-401
The article investigates issues of classification of linear controlled systems under a change of coordinates in their state
and input spaces. The classification problem is completely solved for n-dimensional systems with (n − 1)-dimensional inputs; polynomial relative
GLn( \mathbbC ) ×GLm( \mathbbC ) G{L_n}\left( \mathbb{C} \right) \times G{L_m}\left( \mathbb{C} \right) -invariants on the space of controlled systems are computed. 相似文献
20.
Ian M. Wanless 《Combinatorica》2006,26(6):743-745
Let
denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that
is asymptotically equal to (k−1)k−1k2−k. This confirms Conjecture 23 in Minc's catalogue of open problems.
* Written while the author was employed by the Department of Computer Science at the Australian National University. 相似文献
|