图G_n的优美表示

将给出三个结果:(i)如果图G是SZ(|S|=n≥2)上的整数和图,那么0∈S当且仅当图G至少有一个(n-1)度顶点;(ii)图G(G≠K2)是至少有两个零点的整数和图当且仅当G■K2·Gn;(iii)设图G(G≠K2)是SZ上的整数和图,|S|=n+2,n∈N+.若图G至少有两个零点,则S={mx|m=-1,0,1,2,…,n;x∈Z且x≠0}.     

联接图中的最长链

一、引言文中未加说明的述语均同于[1]。给定图 G,以 c(G)记其联通分支数,定义h(G)=min{|s|-c(G\S):S(?)V(G),c(G\S)>1},f(G)=min{d(u) d(v):u、v∈v(G),u=v,uv(?)E}。1978年 H.A.Jung 在[2]中证明了,当 f(G)≥n(G)-4,n(G)≥11,h(G)≥0时,G 含哈密顿圈。本文研究了上述参数与图中最长链所含点数 l(G)之间的关系,得到下述结果:     

奇图的匹配可扩性

设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.     

完全二部图K_(1,n),K_(2,n)和K_(3,n)的点强可区别全染色

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2.     

关于2012年高考北京卷压轴题构造性证明的思考

试题再现:设A是由m×n个实数组成的m行n列的数表,满足:每个数的绝对值不大于1,且所有数的和为零.记S(m,n)为所有这样的数表构成的集合.对于A∈S(m,n),记ri(A)为A的第i行各数之和(1≤i≤m),cj(A)为A的第j列各数之和(1≤j≤n),记k(A)为|r1(A)|,|r2(A)|,…,|rm(A)|,|c1(A)|,|c2(A)|,…,|cn(A)|中的最小值.(3)给定正整数t,对于所有的A∈S(2,2t+1),求k(A)的最大值.((1),(2)略).本题对学生的思维要求较高,求解的难点在于如何得到k(A)的上界,并通过构造实例说明该上界可以取到.另外,"A∈S(2,2t+1)"的特殊形式     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

椭圆、双曲线中的两类最值问题

1　问题的提出例 1　如图 1 ,已知双曲线 x24- y2 =1 ,过右焦点 F2 作直线 l与双曲线右支交于 A、B两点 ,设左焦点为 F1,求 | F1A| .| F1B|的最小值 .图 1分析 1　在双曲线 x24- y2 =1中 ,a =2 ,b=1 ,c = 5,F1( - 5,0 ) ,F2 ( 5,0 ) ,e =52 .为了书写方便 ,不妨设| F1A| =m,| F1B| =n,即求 m .n的最小值 .若求出 A、B的坐标 ,再求| F1A| .| F1B| ,显然比较复杂 .由双曲线的定义 :　 m - | F2 A| =4,n - | F2 B| =4,m .n =( 4 | F2 A| ) ( 4 | F2 B| )　 =1 6 4 ( | F2 A| | F2 B| ) | F2 A| .| F2 B|　 =1 6 4 | A…     

Fan型条件对图的匹配的影响(英文)

设G是顶点数为2n且至多含有2(n-c)个奇分支的简单图(1≤c≤n).若不存在G的两个距离为2的顶点,其度均小于c-1,则G的边独立数至少为c,除非G含一类明显的禁用导出子图.特别,我们给出了Fan(-1)-型图含有1-因子的充要条件.     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

一个最小可行图的判定条件

设有n个集合X_1,…,X_n,一个以X=U_(i=1)~nX_i为顶点集的图G称为是一个关于(X_1,…,X_n)的可行图,如果对每一个X_i(i=1,…,n),导出子图G_i=G[Xi]是连通的。关于集合序列(X_1,…,X_n),含最少边数的可行图称为是最小可行图。本文证明,关于(X_1,X_2,X_3)的可行图G=G_1∪G_2∪G_3是最小可行图的充分必要条件是:当X_i∩X_j∩X_k≠φ(i,j,k)=1,2,3)时,G_i∩G_j∩G_k是树。它发展了由D.-Z.Du(堵丁柱)在1986年得到的一个结果。     

论局部乘积与POINCARE-ALEXANDER-LEFSCHETZ型对偶定理

<正> 在§1我们界说了局部乘积,它关联 Hausdorff 紧致空间 X 中闭子集X_0的同调以及 X_0在 X 中邻域的同调.在流形与有边流形上的 Poincaré-Alexander-Lefschetz 型对偶定理可以用这种局部乘积表示(§2).在§3,我们研讨了一类所谓摹流形状空间.局部的下调群与上调群的概念在 [3,233—263页;8]中曾不明显地使     

U-统计量的精致渐近性

设{X_n．n≥1}是一非退化的i．i．d．随机变量序列,U_n是以二维Borel可测对称函数h(x,y)为核函数的U-统计量．记U_n=2/(n(n-1))Σ_≤i≤j≤nh(X_i,X_j)．本文分别在核函数h(x,y)只有4/3阶矩或4/3+δ,0＜δ≤1的情况下,对非常广泛的一类权函数(x)与边界函数b(x)得到了如下关于U-统计量U_n的精致渐近性:不仅使得已有的结果成为我们的特况,还大大降低了其中的矩条件．     

一類三角和數的表示式及其近似估值

<正> §1.本文的主要目的是要證明下面的結果: 定理1.設q_1,q_2為二正整數.合     

On Factorisations and Generators in Transformation Semigroups

It is shown that the classical decomposition of permutations into disjoint cycles can be extended to more general mappings by means of path-cycles, and an algorithm is given to obtain the decomposition. The device is used to obtain information about generating sets for the semigroup of all singular selfmaps of $X_{n} = \{1, 2, \dots, n\}$. Let $T_{n,r} = S_{n}\cup K_{n,r}$, where $S_{n}$ is the symmetric group and $K_{n,r}$ is the set of maps $\alpha\,:\, X_{n} \to X_{n}$ such that $|im(\alpha)| \le r$. The smallest number of elements of $K_{n,r}$ which, together with $S_{n}$, generate $T_{n,r}$ is $p_{r}(n)$, the number of partitions of $n$ with $r$ terms.     

Zur lokalen Werteverteilung der Lösungen linearer Differentialgleichungen

Every solution w of the linear differential equation (*) $$L_n (w) = w^{(n)} + a_{n - 1^{w^{(n - 1)} } } + \ldots + a_0 w = 0$$ with polynomial coefficients a_j is a polynomial or an entire function of finite order λ>0. In this paper we prove the following theorem: Let w be a solution of (*) and no polynomial. Let further λ be the order of w and n_a (R, 1/(w?c)) the number of the zeros in the disc |z?a|4^1/λ $$n_a \left( {L|a|^{1 - \lambda } ,1/(w - c)} \right) \leqq N.$$ It is also shown, that for certain solutions of (*) there exists a constant r₀>0 such that we can replace N by n+α for |a|> r₀. α₀ is the degree of the polynomial a₀. An important tool for the proofs is the index of an entire function.     

Finite groups with an almost regular automorphism of order four

P. Shumyatsky’s question 11.126 in the “Kourovka Notebook” is answered in the affirmative: it is proved that there exist a constant c and a function of a positive integer argument f(m) such that if a finite group G admits an automorphism ϕ of order 4 having exactly m fixed points, then G has a normal series G ⩾ H ⩽ N such that |G/H| ⩽ f(m), the quotient group H/N is nilpotent of class ⩽ 2, and the subgroup N is nilpotent of class ⩽ c (Thm. 1). As a corollary we show that if a locally finite group G contains an element of order 4 with finite centralizer of order m, then G has the same kind of a series as in Theorem 1. Theorem 1 generalizes Kovács’ theorem on locally finite groups with a regular automorphism of order 4, whereby such groups are center-by-metabelian. Earlier, the first author proved that a finite 2-group with an almost regular automorphism of order 4 is almost center-by-metabelian. The proof of Theorem 1 is based on the authors’ previous works dealing in Lie rings with an almost regular automorphism of order 4. Reduction to nilpotent groups is carried out by using Hall-Higman type theorems. The proof also uses Theorem 2, which is of independent interest, stating that if a finite group S contains a nilpotent subgroup T of class c and index |S: T | = n, then S contains also a characteristic nilpotent subgroup of class ⩽ c whose index is bounded in terms of n and c. Previously, such an assertion has been known for Abelian subgroups, that is, for c = 1. __________ Translated from Algebra i Logika, Vol. 45, No. 5, pp. 575–602, September–October, 2006.     

Strong Convergence for Weighted Sums of Negatively Associated Arrays

Let {Xni} be an array of rowwise negatively associated random variables and Tnk=k∑i=1 i^a Xni for a ≥ -1, Snk =∑｜i｜≤k Ф（i/nη）1/nη Xni for η∈（0,1],where Ф is some function. The author studies necessary and sufficient conditions of ∞∑n=1 AnP（max 1≤k≤n｜Tnk｜〉εBn）〈∞ and ∞∑n=1 CnP（max 0≤k≤mn｜Snk｜〉εDn）〈∞ for all ε 〉 0, where An, Bn, Cn and Dn are some positive constants, mn ∈ N with mn /nη →∞. The results of Lanzinger and Stadtmfiller in 2003 are extended from the i.i.d, case to the case of the negatively associated, not necessarily identically distributed random variables. Also, the result of Pruss in 2003 on independent variables reduces to a special case of the present paper; furthermore, the necessity part of his result is complemented.     

A Partitioned Version of the Erdös–Szekeres Theorem for Quadrilaterals

We prove a partitioned version of the Erdös–Szekeres theorem for the case $k = 4$: any finite set $X \subset \bbbr^2$ of points in general position can be partitioned into sets $X_0, X_{ij}$ where $i=1,2,3,4$ and $j=1,\ldots,26$, so that $|X_{1j}|=|X_{2j}|=|X_{3j}|=|X_{4j}|$, $|X_0|\leq 4$ and for all $j$ every transversal $\{x_1,x_2,x_3,x_4\}$, $x_1 \in X_{1j}, x_2 \in X_{2j},x_3 \in X_{3j}, x_4 \in X_{4j}$, is in convex position. In order to prove this, we show another theorem, the partitioned version of the same type lemma, which was proved by Bárány and Valtr.     

Bipartite Graphs Kn,n+r- A (|A| ≤ 3) Determined by Their Cycle Length Distributions

The cycle length distribution of a graph G of order n is a sequence (c1 (G),..., cn (G)), where ci(G) is the number of cycles of length i in G. In general, the graphs with cycle length distribution (c1(G),...,cn(G)) are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution (c1 (G),..., cn (G)) is unique. Let Kn,n+r be a complete bipartite graph and A(∈)E(Kn,n+r). In this paper, we obtain: Let s > 1 be an integer. (1) If r = 2s, n > s(s - 1) + 2|A|, then Kn,n+r - A (A(∈)E(Kn,n+r),|A| ≤ 3) is determined by its cycle length distribution; (2) If r = 2s + 1,n > s2 + 2|A|, Kn,n+r - A (A(∈)E(Kn,n+r), |A| ≤ 3) is determined by its cycle length distribution.     

在最少条件下的对数律精确渐近性

设$X_1,X_2,\cdots$为独立同分布随机变量, 记S_n=X_1+\cdots+X_n,\;M_n=\max\limits_{k\le n}|S_k|,\;n\ge1$. 本文在充分必要条件下给出了$M_n$和$S_n$的对数律之精确渐近性.