有向图的拉普拉斯谱半径的几个上界

设G=(V(G),E(G))是一个简单有向图具有顶点集V(G)={v_1,v_2,…,v_n)和弧集E(G).用d_i~+表示顶点v_i的出度.设A(G)是有向图G的邻接矩阵和D(G)=diag(d_1~+,d_2~+,…,d_n~+)有向图G的顶点出度对角矩阵,则称L(G)=D(G)-A(G)为有向图G的拉普拉斯矩阵.L(G)的谱半径称作有向图G的拉普拉斯谱半径,用A(G)表示.在这篇文章中,给出了关于A(G)的一些上界,进而一些关于λ(G)涉及有向图G的出度和二次平均出度的上界也被得到.最后,我们举例对这些上界进行了比较.     

有向图n·Cm的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f':E(D)→{1,2,…,|E|}是一个双射函数,其中,f'(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f'称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n·Cm的优美性,并且证明了当m=23且n为偶数时,n·Cm是优美有向图.     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.     

关于循环有向图的弧强连通度

设D=(V,A)为简单有向图,其中V=V(D)和A=A(D)分别表示D的顶点集合和弧集合。x,y∈V(D),xy∈A(D)表示D中从x到y的弧。有向图D称为强连通的如果对D中任何两顶点u和v,D中有一条从u到v的有向路,也有一条从v到u的有向路。     

五类特殊图的三种距离矩阵的特征多项式

设G是一个具有顶点集V(G)={v_1,v_2,…,u_n}的n阶简单图.设d_(i,j)=d(v_i,v_j)表示图G中任意两个顶点v_i与v_j的距离.矩阵D(G)=[d_(i,j)]_(n×n)定义为图G的距离矩阵.定义Tr(v)=∑_(ueV(G))d(u,u)为图G中顶点u的点传递度.Diag(Tr)表示以G中顶点的点传递度为主对角线上元素的对角矩阵.则矩阵D~L(G)=Diag(Tr)一D(G)和D~Q(G)=Diag(Tr)+D(G)分别定义为图G的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.分别得到五类特殊图的距离,距离拉普拉斯,距离无符号拉普拉斯的特征多项式的一般表达式.     

边色数的分类及其有关性质

设图G为简单连通图,由Vizing定理知:Δ(G)≤x′(G)≤Δ(G) 1,其中Δ(G)表示图G的最大顶点次,x′(G)为图G的边色数。若x′(G)=Δ(G),则称G为第一类图,记为G∈C~1;若x′(G)=Δ(G) 1,则称G为第二类图,记为G∈C~2。其他图论术语见一般参考书。一边e(或者顶点v)称为临界的,如果成立x′(G)>x′(G\e)(或者x′(G)>x′(G\v))。图G称为是临界的,如果G∈C~2,且G的每一边是临界的。对于v∈V(G),令d~*(v)=|{u|(v,u)∈E(G)且d(u)=Δ(G)}|。设F={u|d(u)=Δ(G),u∈V(G)},记G_Δ=G[F]。令图G_Δ的圈秩数为b(G_Δ)。     

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下:     

具有给定指数的本原有向东图的Hamilton性质

本文解决了1982年J.A.Ross提出的两个问题,并得到如下结果(1) 设D是具有围长s>1　　和指数γ(D)=n+s(n-2)的n阶本原有向图,则D是Hamilton的; (2)设D是含有环的n阶本原有向图且γ(D)=2n-2,则D是Hamilton的当且仅当max{d(u,v)|γ(u,v)=2n-2}=n-2     

局部内(外)半完全有向图可迹的充分条件

本文利用多重插入法,对局部内(外)半完全有向图及其扩张有向图的可迹性作了讨论.首先,证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}满足d(x)≥n-1,d(可)≥n-2,或d(x)≥n-2,d(y)≥n-1,则D是可迹的.同时还证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}有min{d~+(x)+d~-(y),d~-(x)+d~+(y)}≥n-1,D是可迹的.其次,证明了n阶连通的扩张局部内半完全有向图D,如果任意不相邻的控制点对{u,v}和任意不相邻的受控点对{x,y}同时满足(1)d(u)≥n-1,d(v)≥n-1;(2)d(x)≥n-1,d(y)≥n-2或d(x)≥n-2,d(y)≥n-1,则D是可迹的.最后,利用逆图的性质把这三个结论推广到n阶连通的局部外半完全有向图与n阶连通的扩张局部外半完全有向图中.     

一类满足Adám猜想的循环图

设n为大于1的整数,K是Z/(n)的任一非空子集,G_n(K)是以V(G)={V_0,V_1,…,V_(n-1)}为顶点,E(G)为边集的有向图,其中(V_i,V_j)∈E(G),当且仅当(j-i)∈K。Adm在[1]中猜测G_n(K)≌G_n(K′)当且仅当存在Z/(n)中的单位u使得K′=uK。可惜这个猜想是不正确的。于是产生这样的问题:在什么情况下Adm猜想是成立的?这方面的进展情况见孙良的详细综述[2]。本文讨论一种特殊的情况。     

Distribution of types of symmetry of tensors of high degree

The asymptotic distribution of tensors of degree N in symmetry types is studied in this paper.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 155, pp. 181–186, 1986.     

Estimates of stability of characterization of additive types of distributions

An estimate of stability of characterization of distribution types is obtained for the case of additive types. Under some conditions, the estimate has the order ε^1/3L(ε), where L(ε) is a slowly varying function. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow, Russia, 1996, Part I.     

Study of the blow-up of solutions of systems of equations of hydrodynamic type

Mathematical Notes - We study the initial boundary-value problem for three-dimensional systems of equations of pseudoparabolic type. The system is similar to the Oskolkov system, but differs from...     

一类完全正则半群簇子簇格的性质

本文研究了完全正则半群簇的子簇格［Ｖ＋∩ＰＶ，Ｖ＋∩ＰＶ］的某些格运算性质，我们证明了簇Ｖ＋∩ＰＶ可分解为Ｖ与Ｖ＋∩ＰＶ的并；对任意完全正则半群簇Ｗ，有Ｗ∩（Ｖ∨Ｖ＋∩ＰＶ）＝（Ｗ∩Ｖ）∨（Ｗ∩Ｖ＋∩ＰＶ）．特别地，我们得到了等式Ｖ＋∩ＰＶ＝Ｖ成立的若干条件．     

Characterization of types of asymptotic discernibility of families of hypotheses

We give a characterization of the types of asymptotic discernibility of families of hypotheses in the case of hypothetical measures that are not, in general, mutually absolutely continuous. The case when the logarithm of the likelihood ratio admits an asymptotic expansion of the type of an expansion with local asymptotic normality is examined in detail. Examples are studied.Translated fromTeoriya Sluchainykh Protsessov, Vol. 15, pp. 64–71, 1987.     

Bases of the identities of products of certain varieties of groups

The following theorem is proved: The product of any variety of two-step solvable groups and a variety having a finite basis of identity relations has a finite basis of identity relations.Translated from Matematicheskie Zametki, Vol. 5, No. 1, pp. 137–144, January, 1969.     

Preservation of equivalence of derivations under reduction of depth of formulas

In this paper we consider derivations in the (&, )-fragment of the intuitionistic propositional calculus. As is known, replacement of any occurrence of a formula [F] in a sequent S by an occurrence of the formula [p], where p is a new propositional variable, with the simultaneous addition to the antecedent of the formula F p or p F depending on the sign of the occurrence of F in S, leaves the derivability unchanged. We give a proof of the fact that the natural extension of this transformation to derivations preserves the relation of equivalence of derivations, i.e., transformed derivations are equivalent if and only if the originals are equivalent. (Derivations are considered equivalent if certain of their normal forms coincide, or, what is the same, if their deductive terms coincide.) It is proved that by the iteration of this transformation, each derivation of an arbitrary sequent S can be transformed into a derivation of a sequent S, depending only on S, whose succedent is a variable, and in the antecedent there occur only formulas of the form a,a & b, a b,,(a b) c, a & b c, a (b & c), wherea, b, c are variables. Here if S is balanced, then S is also balanced. (A sequent is called balanced if each variable occurs in it no more than twice.) The familiar correspondence between certain concepts of the theory of categories and concepts of the theory of proofs allows one to assert that there has been constructed a univalent functor, mapping a free Cartesian closed category into itself.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 197–207, 1979.