可容错群测模型(d,r;z]-析取矩阵的新构作

(d,r;z]-析取矩阵是群测理论一个可容错、可纠错的数学模型,它应用于许多领域.利用辛空间上一类子空间的特殊组合给出了(d,r;z]-析取矩阵的一个新构作,并利用子空间的计数定理计算了它的参数.     

可容错群测模型(d,r;z]-析取矩阵的新构作北大核心

(d,r;z]-析取矩阵是群测理论一个可容错、可纠错的数学模型,它应用于许多领域.利用辛空间上一类子空间的特殊组合给出了(d,r;z]-析取矩阵的一个新构作,并利用子空间的计数定理计算了它的参数.     

二元(p,r,d)-码的构作及其应用

令n是一个正整数,[n]={1,2,…,n}.利用集合[叫上的s-子集族((ns))构作了二元(p,r,d)-叠加码,研究了它的容错和析取性质并介绍了它在非适应性群测(Nonadaptive Group Testing)方面的应用.     

Star图互连网络的容错性分析

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时，总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性，然后得到了Star图的限制连通度是2n-4，当n=3,5和n≥7时，它的限制容错直径是|_3(n-1)/2_|+2，对于n =4, 6，限制容错直径是|_3(n-1)/2_|+3，即限制容错直径只比它的容错直径大1。     

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．     

n维有限射影空间上d~e——析取矩阵的新构作

利用n维有限射影空间上的一些性质,构作了组合群验的数学模型de-析取矩阵,并研究了它的参数和Hamming距离.     

广义Fibonacci立方体的网络容错性质分析

主要研究广义Fibonacci立方体的容错直径和宽直径,证明了n维Fibonacci立方体网络的k-1容错直径和k宽直径都是n-1,其中k=[n/3].     

群测模型在多路存取信道中竞争消解方面的应用

非适应性组合群测(group testing)是组合数学的一个分支,它有着广泛的应用.在一个有限集[n]上构作了一个群测模型,并利用这个群测模型介绍了它在多路存取信道中竞争消解方面的应用.     

2p2阶3度Cayley图

Cayley图Cay(G,S)称之为正规的,如果G的右正则表示是Cay(G,S)全自同构群的正规子群。本文决定了2p~2(p为素数)阶群上3度连通Cayley图的正规性,作为该结果的一个应用,对每一个1(?)s(?)5,对2p~2阶3度s-正则Cayley图作了分类。     

变种超方体网络的容错直径与宽直径

研究变种超方体的网络容错直径和宽直径,证明了n维变种超立方体的n-1容错直径和n宽直径为[2n/3]+1或[2n/3]+2.     

Relative difference sets fixed by inversion and Cayley graphs

Using graph theoretical technique, we present a construction of a (30,2,29,14)-relative difference set fixed by inversion in the smallest finite simple group—the alternating group A₅. To our knowledge this is the first example known of relative difference sets in the finite simple groups with a non-trivial forbidden subgroup. A connection is then established between some relative difference sets fixed by inversion and certain antipodal distance-regular Cayley graphs. With the connection, several families of antipodal distance-regular Cayley graphs which are coverings of complete graphs are presented.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

Cayley Snarks and Almost Simple Groups

A Cayley snark is a cubic Cayley graph which is not 3-edge-colourable. In the paper we discuss the problem of the existence of Cayley snarks. This problem is closely related to the problem of the existence of non-hamiltonian Cayley graphs and to the question whether every Cayley graph admits a nowhere-zero 4-flow. So far, no Cayley snarks have been found. On the other hand, we prove that the smallest example of a Cayley snark, if it exists, comes either from a non-abelian simple group or from a group which has a single non-trivial proper normal subgroup. The subgroup must have index two and must be either non-abelian simple or the direct product of two isomorphic non-abelian simple groups. Received January 18, 2000 Research partially supported by VEGA grant 1/3213/96 Research partially supported by VEGA grants 1/3213/96 and 1/4318/97     

Cubic Ramanujan graphs

A fimily of cubic Ramanujan graph is explicitly constructed. They are realized as Cayley graphs of a certain free group acting on the 3-regular tree; this group is obtained from a definite quaternion algebra that splits at the prime 2 and has a maximal order of class number 1.     

Connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two suffcient and necessary conditions for such graphs to be 1- or 2-arc-regular are given and based on the conditions, several infinite families of 1-or 2-arc-regular cubic Cayley graphs of alternating groups are constructed.     

A new bound for neighbor-connectivity of abelian Cayley graphs

For the notion of neighbor-connectivity in graphs, whenever a vertex is “subverted” the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. The main result of this paper is a sharpening of the bound for abelian Cayley graphs. In particular, we show by constructing an effective subversion strategy for such graphs, that neighbor-connectivity is bounded above by ⌈δ/2⌉+2. Using a result of Watkins the new bound can be recast in terms of κ to get neighbor-connectivity bounded above by ⌈3κ/4⌉+2 for abelian Cayley graphs.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

On a pursuit game on cayley graphs

The game cops and robbers is considered on Cayley graphs of abelian groups. It is proved that if the graph has degreed, then [(d+1)/2] cops are sufficient to catch one robber. This bound is often best possible.     

Energy of unitary Cayley graphs and gcd-graphs

This work is based on ideas of Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009) 1881-1889] on the energy of unitary Cayley graph. For a finite commutative ring R with unity , the unitary Cayley graph of R is the Cayley graph whose vertex set is R and the edge set is {{a,b}:a,b∈Randa-b∈R^×}, where R^× is the group of units of R. We study the eigenvalues of the unitary Cayley graph of a finite commutative ring and some gcd-graphs and compute their energy. Moreover, we obtain the energy for the complement of unitary Cayley graphs.     

The non-orientable genus of some metacyclic groups

We describe non-orientable, octagonal embeddings for certain 4-valent, bipartite Cayley graphs of finite metacyclic groups, and give a class of examples for which this embedding realizes the non-orientable genus of the group. This yields a construction of Cayley graphs for which is arbitrarily large, where and are the orientable genus and the non-orientable genus of the Cayley graph.Work supported in part by the Research Council of Slovenia, Yugoslavia and NSF Contract DMS-8717441.Supported by NSF Contract DMS-8601760.