有向图的边割(X,Y)中｜X｜和｜Y｜的下界与有向图的极大性和超级性

在已有的极大边连通、超级边连通、极大局部边连通有向图概念的基础上,提出超级局部边连通有向图的概念,对一般的、二部的、基础图的团数至多为p的有向图、定向图分别给出｜(X,Y)｜＜δ(D)的边割(X,Y)、非平凡的最小边割(X,Y)中｜X｜和｜Y｜的下界,据此分别得到极大边连通、超级边连通有向图的最小度条件.类似地分别得到...     

非负矩阵与有向图的谱半径

本文给出非负矩阵的谱半径的上界、下界,由此给出有向图的谱半径的界.     

关于图的直径和平均距离

图的直径和平均距离是度量网络有效性的两个重要参数．Ore通过图的顶点数和直径给出无向图的最大边数．Entringer，Jakson，Slater和Ng，Teh通过图的顶点数和边数分别给出无向图和有向图平均距离的下界．该文提供这两个结果的简单证明，给出有向图类似Ore的结果，并通过图的直径改进Entringer等人的结果到更一般的情形．结合本文和Ore的结果，可以得到一个无向图和有向图平均距离的下界，它比Plesnik得到的下界更好．     

广义de Bruijn和Kautz有向图的距离控制数

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .     

本原极小强连通有向图1—指数的下界

本文给出了n阶本原极小强连通有向图1-指数的下图:expD(1)4.且这个下界是可以达到的.     

若干有向图的SAS-全染色

提出了有向图的SAS-全染色的概念,有向图D的SAS-全染色是D的一个正常全染色,若对D中点染色来说,不存在长为3的2色有向路.对D中弧染色来说,不存在长为4的2色有向路.并定义了有向图D的SAS-全色数,记为(D).用构造染色的方法给出了一些特殊有向图(有向路,有向圈,定向轮,定向扇,有向双星)的SAS-全色数.     

具有g个零强分支的有向图的传递指数

研究了传递矩阵的图论,及布尔矩阵幂的若干图论性质,给出了有向图(布尔矩阵)传递指数的上、下界估计,从而改进了已有的结果.     

广义de Bruijn和Kautz有向图的双向控制集

设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

有向图的Laplace谱半径

Laplace矩阵的谱半径一直是近年来谱图理论的研究热点.本文主要讨论有向图Laplace矩阵的谱半径,用顶点的出度和公共邻域数给出了谱半径上界,用图的最大出度给出了一些特殊图类谱半径的下界.     

有向图的距离标号边跨度

将无向图距离标号边跨度的概念引入到有向图.运用图的流（flow）及tension理论,确定了有向树和有向圈的边跨度,以及最长有向路长不超过3的有向二部图边跨度的可达上下界.     

Induced cayley graphs and d0ouble covers

Motivated by a construction of highly expanding simple Cayley graphs of dihedral groups derived from-or induced by-highly expanding Cayley digraphs fo cyclic groups presented by F. R. K. chung, constructions of simple Cayley graphs on a semidirect product of groups and Cayley digraphs of one of its factors are suggested. In case of the non-normal factor being the cyclic group of order 2. a condition is given to derive spectral bounds of the Cayley graph of the product from those of the Cayley graph of the normal factor.     

An extended duality theorem and multiplication of several matrices

Motivated by a construction of highly expanding simple Cayley graphs of dihedral groups derived from-or induced by-highly expanding Cayley digraphs fo cyclic groups presented by F. R. K. chung, constructions of simple Cayley graphs on a semidirect product of groups and Cayley digraphs of one of its factors are suggested. In case of the non-normal factor being the cyclic group of order 2. a condition is given to derive spectral bounds of the Cayley graph of the product from those of the Cayley graph of the normal factor.     

一类非正规Cayley有向图

本文研究了2p2(p奇素数)阶非交换群上两度Cayley有向图的正规性,发现 了一无限族非正规的Cayley有向图.     

Switching Reconstruction of Digraphs

Switching about a vertex in a digraph means to reverse the direction of every edge incident with that vertex. Bondy and Mercier introduced the problem of whether a digraph can be reconstructed up to isomorphism from the multiset of isomorphism types of digraphs obtained by switching about each vertex. Since the largest known nonreconstructible oriented graphs have eight vertices, it is natural to ask whether there are any larger nonreconstructible graphs. In this article, we continue the investigation of this question. We find that there are exactly 44 nonreconstructible oriented graphs whose underlying undirected graphs have maximum degree at most 2. We also determine the full set of switching‐stable oriented graphs, which are those graphs for which all switchings return a digraph isomorphic to the original.     

A Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

Cliques that are tolerance digraphs

In this paper, we study directed graph versions of tolerance graphs, in particular, the class of totally bounded bitolerance digraphs and several subclasses. When the underlying graph is complete, we prove that the classes of totally bounded bitolerance digraphs and interval catch digraphs are equal, and this implies a polynomial-time recognition algorithm for the former class. In addition, we give examples (whose underlying graphs are complete) to separate every other pair of subclasses, and one of these provides a counterexample to a conjecture of Maehara (1984).     

The kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs

In this article, we study the kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs. A bound on the kth upper bases for primitive nonpowerful minimally strong signed digraphs is obtained, and the equality case of the bound is characterized. For the kth lower bases, we obtain some bounds. For some cases, the bounds are best possible and the extremal signed digraphs are characterized. We also show that there exist ‘gaps’ in both the kth upper base set and the kth lower base set of primitive nonpowerful minimally strong signed digraphs.     

Cayley Digraphs of Finite Simple Groups with Small Out-Valency

Abstract

For a group G and a subset S of G which does not contain the identity of G, the Cayley digraph Cay(G, S) is called normal if R(G) is normal in Aut(Γ). In this paper, we investigate the normality of Cayley digraphs of finite simple groups with out-valency 2 and 3. We give several sufficient conditions for such Cayley digraphs to be normal. By using this result, we consider the digraphical regular representations of finite simple groups.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

Limit points of eigenvalues of (di)graphs

The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph D, the set of limit points of eigenvalues of iterated subdivision digraphs of D is the unit circle in the complex plane if and only if D has a directed cycle. 3. Every limit point of eigenvalues of a set D of digraphs (graphs) is a limit point of eigenvalues of a set of bipartite digraphs (graphs), where consists of the double covers of the members in D. 4. Every limit point of eigenvalues of a set D of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in D. 5. If M is a limit point of the largest eigenvalues of graphs, then −M is a limit point of the smallest eigenvalues of graphs.