强正则图的一些性质

文[3]给出了强正则图的概念及有关性质,本文在此基地上利用图的谱性质,得到了强正则图的又一些性质。     

Abelian正则环的零因子图

We introduce the zero-divisor graph for an abelian regular ring and show that if R, S are abelian regular, then (K0(R),[R])≌(K0(S),[S])if and only if they have isomorphic reduced zero-divisor graphs. It is shown that the maximal right quotient ring of a potent semiprimitive normal ring is abelian regular,moreover,the zero-divisor graph of such a ring is studied.     

A Classification of Regular Embeddings of Graphs of Order a Product of Two Primes

In this paper, we classify the regular embeddings of arc-transitive simple graphs of order pq for any two primes p and q (not necessarily distinct) into orientable surfaces. Our classification is obtained by direct analysis of the structure of arc-regular subgroups (with cyclic vertex-stabilizers) of the automorphism groups of such graphs. This work is independent of the classification of primitive permutation groups of degree p or degree pq for p q and it is also independent of the classification of the arc-transitive graphs of order pq for p q.     

On the Toughness of Cycle Permutation Graphs

Motivated by the conjectures in [11], we introduce the maximal chains of a cycle permutation graph, and we use the properties of maximal chains to establish the upper bounds for the toughness of cycle permutation graphs. Our results confirm two conjectures in [11].     

Algebraic Properties of Edge Ideals of Some Vertex-Weighted Oriented Cyclic Graphs

We provide some exact formulas for the projective dimension and regularity of edge ideals associated to some vertex-weighted oriented cyclic graphs with a common vertex or edge.These formulas are functions in the weight of the vertices,and the numbers of edges and cycles.Some examples show that these formulas are related to direction selection and the assumption that w(x)≥2 for any vertex x cannot be dropped.     

有关循环图C(n;{1,k})的独立数的一些结果

令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值.     

最大2-正则诱导子图的长度

设G是2-连通图，c(G)是图G的最长诱导圈的长度，c′(G)是图G的最长诱导2-正则子图的长度。本文我们用图的特征值给出了c(G)和c′(G)的几个上界。     

On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs

Let F(x)=∑∞n=1 Tsi,s2,...,sk(n)x^n be the generating function for the number,Ts1bs2,...,sk(n) of spanning trees in the circulant graph Cn(s1,S2,...,Sk).We show that F(x)is a rational function with integer coefficients satisfying the property F(x)=F(l/x).A similar result is also true for the circulant graphs C2n(s1,S2,....,Sk,n)of odd valency.We illustrate the obtained results by a series of examples.     

Minimal Characteristic Algebras for Some Properties of Identities

We consider algebras of a type , without nullary fundamental operation symbols. A structural property p of an identity of type is hereditary if for every set I of identities of type having the property p every consequence of I (derived identity) has the property p. An algebra of type we call characteristic for a hereditary property p if for every variety V of type we have: V if and only if every identity from Id(V) has the property p. In this paper we show minimal characteristic algebras for several hereditary properties, e.g., to be regular, to be normal, etc.1991 Mathematics Subject Classification 08B05     

Some sufficient conditions for a planar graph of maximum degree six to be Class 1

Let G be a planar graph of maximum degree 6. In this paper we prove that if G does not contain either a 6-cycle, or a 4-cycle with a chord, or a 5- and 6-cycle with a chord, then χ^′(G)=6, where χ^′(G) denotes the chromatic index of G.     

The conjugacy problem for Dehn twist automorphisms of free groups

A Dehn twist automorphism of a group G is an automorphism which can be given (as specified below) in terms of a graph-of-groups decomposition of G with infinite cyclic edge groups. The classic example is that of an automorphism of the fundamental group of a surface which is induced by a Dehn twist homeomorphism of the surface. For , a non-abelian free group of finite rank n, a normal form for Dehn twist is developed, and it is shown that this can be used to solve the conjugacy problem for Dehn twist automorphisms of . Received: February 12, 1996.