随机图ξ（n,M）上随机游动的平均返回时间

设 G 是一个连通图,G 上的随机游动是如下的马氏链:其状态空间是 G 的顶点集,从一个顶点总是以等概率转移到相邻的顶点。用 E_(n,M)(k)表示在全体具有 n 个顶点 M 条边的连通图上,随机游动回到具有次数为 h 的项点所用的平均时间。我们得到了以下结果:对任意固定实数 c,令 M_o=[1/2nl_n+cn],那么当→∞时,     

含有大的悬挂树图的Ramseygoodness结论(英文)

设H是阶为n的连通图.在H的某一个顶点上悬挂一棵阶为j的树,得到图H_j,用H_j表示这样的图形族.本文证明:当j充分大时,有r(G,H_j)=(x(G)-1)(n+j-1)+s(G),其中x(G),s(G)分别表示图G的色数和色数剩余.     

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

设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的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.分别得到五类特殊图的距离,距离拉普拉斯,距离无符号拉普拉斯的特征多项式的一般表达式.     

拟阵Q6与W4可F-线性表示的构造

对拟阵Q6与W4可F-线性表示的构造进行了研究.用E(G)在R上的链群F0(G,R)表示G的圈拟阵M(G);用松弛拟阵M的极小圈超平面X的方法得到拟阵M'.得到主要结果为:(i)用链群表示了M(K4),M(W4);(ii)用松弛极小圈超平面的方法从M(K4)构造了Q6,从M(W4)构造了W4,找出了W4可线性表示的所有...     

关于n-连通图的完美匹配与最大匹配

ξ1.引言本文所考虑的图均指无自环、无重边、无向有限的连通图,没有特别指明的术语见[1].以V(G)、E(G)分别表示图C的顶点集与边集. 设M是图G的一个支撑子图.若M的每个顶点的度是0或者1,则称M是G的一个匹配,若M是G的匹配中边数最多的一个,则称M是G的一个最大匹配;若M是G的匹配,且M中无0度顶点,则称M是G的一个完美匹配. 图G称为n连通的,若对G的任意两个不同的顶点x,y,G中存在n条以x,y为端点     

关于复Finsler流形的一个注记

设(M,G)为n维复Finsler流形,TM为M的全纯切丛,得到了TM上的Hermite度量hTM=G(-ij)(z,v)dzi(×)d(-z)j+G(-ij)(z,v)δvi(×)δ(-v)j为K(a)hler度量的充要条件是M为全纯曲率为0的Kahler流形,其中G(-ij)=(а)2G/(а)vi(а)(-v)j,1≤i,j≤n.推广了Cao-Wong的某些结果.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

有限循环群上的 Cayley 有向图的哈密顿回路

给定有限循环群G及其特征集M(记为 G=〈M〉),在G上以M为特征集的Cayley有向图Γ(M,G) 定义如下:Γ(M,G)的顶点为 G 的元,当且仅当 g∈G,s∈M 时,在Γ(M,G)中存在一条从 g 到 gs 的弧.本文所指的群均为至少有三个元的有限群,其特征集 M 均不含单位元.有限集 E 的元的个数记为|E|.令 T=[t_1,t_2,…,t_r](表示序列),n 为正整数,n 个 T 排成的序列记为 n*T.例如,T=[t_1,t_2],2*T=[t_1,t_2,t_1,t_2].     

几类图的匹配唯一性

若图G的匹配多项式为M(G;W),对任何图H,M(G;W)=M(H;W)推出G与H同构,则称G是匹配唯一的.本文讨论了下面的几种图类:(i)B_(m,n,r);(ii)D_(m,n,r);(iii)T_(m,n)的匹配唯一性问题,从而得到一些较为满意的结果.     

单圈图的无符号拉普拉斯埃斯特拉达指数（英文）

设G是一个具有n个顶点的简单图.矩阵Q(G)=D(G)+A(G)表示图G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别表示图G的顶点度对角矩阵和邻接矩阵.图G的无符号拉普拉斯埃斯特拉达指数定义为QEE(G)=∑_(i=1)~ne~(λ_i(G)),其中λ_1(G)≥λ_2(G)≥…λ_n(G)是指图G的无符号拉普拉斯特征值.本文确定了具有最大的无符号拉普拉斯埃斯特拉达指数的唯一的n个顶点的单圈图.     

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

Minimum vertex covers and the spectrum of the normalized Laplacian on trees

We show that, in the graph spectrum of the normalized graph Laplacian on trees, the eigenvalue 1 and eigenvalues near 1 are strongly related to minimum vertex covers.In particular, for the eigenvalue 1, its multiplicity is related to the size of a minimum vertex cover, and zero entries of its eigenvectors correspond to vertices in minimum vertex covers; while for eigenvalues near 1, their distance to 1 can be estimated from minimum vertex covers; and for the largest eigenvalue smaller than 1, the sign graphs of its eigenvectors take vertices in a minimum vertex cover as representatives.     

扭的Heisenberg-Virasoro顶点算子代数的一个特征化（英文）

The twisted Heisenberg-Virasoro algebra is the universal central extension of the Lie algebra of differential operators on a circle of order at most one. In this paper, we first study the variety of semi-conformal vectors of the twisted Heisenberg-Virasoro vertex operator algebra, which is a finite set consisting of two nontrivial elements. Based on this property,we also show that the twisted Heisenberg-Virasoro vertex operator algebra is a tensor product of two vertex operator algebras. Moreover, associating to properties of semi-conformal vectors of the twisted Heisenberg-Virasoro vertex operator algebra, we charaterized twisted Heisenberg-Virasoro vertex operator algebras. This will be used to understand the classification problems of vertex operator algebras whose varieties of semi-conformal vectors are finite sets.     

The algebraic structure of relative twisted vertex operators

Twisted vertex operators based on rational lattices have had many applications in vertex operator algebra theory and conformal field theory. In this paper, “relativized” twisted vertex operators are constructed in a general context based on isometries of rational lattices, and a generalized twisted Jacobi identity is established for them. This result generalizes many previous results. Relatived untwisted vertex operators had been studied in a monograph by the authors. The present paper includes as a special case the proof of the main relations among twisted vertex operators based on even lattices announced some time ago by the second author.     

Vertex coalgebras, comodules, cocommutativity and coassociativity

We introduce the notion of vertex coalgebra, a generalization of vertex operator coalgebras. Next we investigate forms of cocommutativity, coassociativity, skew-symmetry, and an endomorphism, D^∗, which hold on vertex coalgebras. The former two properties require grading. We then discuss comodule structure. We conclude by discussing instances where graded vertex coalgebras appear, particularly as related to Primc’s vertex Lie algebra and (universal) enveloping vertex algebras.     

Vertex covers and eternal dominating sets

The eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a vertex with no guard is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow any number of guards to move to neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the vertex cover number of a graph. One of our main results is that the eternal domination number is less than the vertex cover number of any graph of minimum degree at least two having girth at least nine.     

关于局部顶点李代数的一些注记

本文研究局部顶点李代数与顶点代数之间的关系.利用由局部顶点李代数构造顶点代数的方法,定义局部顶点李代数之间的同态,证明了同态可以唯一诱导出由局部顶点李代数构造所得到的顶点代数之间的同态.     

Approximating the maximum vertex/edge weighted clique using local search

This paper extends the recently introduced Phased Local Search (PLS) algorithm to more difficult maximum clique problems and also adapts the algorithm to handle maximum vertex/edge weighted clique instances. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, where vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in firstly their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree, or random selecting within vertex penalties that are dynamically adjusted during the search. Secondly, the perturbation mechanism used to overcome search stagnation differs between the sub-algorithms. PLS has no problem instance dependent parameters and achieves state-of-the-art performance for maximum clique and maximum vertex/edge weighted clique problems over a large range of the commonly used DIMACS benchmark instances.     

A theory of tensor products for module categories for a vertex operator algebra, III

This is the third part in a series of papers developing a tensor product theory for modules for a vertex operator algebra. The goal of this theory is to construct a “vertex tensor category” structure on the category of modules for a suitable vertex operator algebra. The notion of vertex tensor category is essentially a “complex analogue” of the notion of symmetric tensor category, and in fact a vertex tensor category produces a braided tensor category in a natural way. In this paper, we focus on a particular element P(z) of a certain moduli space of three-punctured Riemann spheres; in general, every element of this moduli space will give rise to a notion of tensor product, and one must consider all these notions in order to construct a vertex tensor category. Here we present the fundamental properties of the P(z)-tensor product of two modules for a vertex operator algebra. We give two constructions of a P(z)-tensor product, using the results, established in Parts I and II of this series, for a certain other element of the moduli space. The definitions and results in Parts I and II are recalled.     

Rubbling and optimal rubbling of graphs

A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move one pebble is removed at vertices v and w adjacent to a vertex u and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number of a graph is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We determine the rubbling and optimal rubbling number of some families of graphs and we show that Graham’s conjecture does not hold for rubbling numbers.