简单有向图谱半径的界

设 G为 n阶简单连通有向图 ,ρ(G)为图 G的邻接谱半径 .本文利用代数方法研究了简单有向图谱半径的性质并给出了ρ(G)的界 .

简单有向图所有单向分图的求解算法

文章提出了一种简单有向图所有单向分图的求解算法,该算法数据结构形式简单,求解方便且易于实现.用C语言设计了相应的程序验证了此算法.

简单有向图情形下Adfm猜想的证明

就简单有向图情形下证明了Ａｄáｍ关于“若Ｄ是包含有向圈的有向图，则存在某弧，把它反向后将减少Ｄ中有向圈的数目”

有向图n·■_9的优美性

设Cm表示具有m个顶点的有向圈,n·Cm表示由仅具有一个公共顶点的n有向圈Cm组成的有向图.1994年杜之亭,孙惠泉在证明了n·C2p(n≡0(mod2))是优美图的基础上提出猜想"n·C2p+1(n≡0(mod2))是优美的",之后,很多学者在这方面做了大量的工作,并分别证明了猜想对于p=1,2,3是成立的.本文证明了猜想对于p=4(即有向图n·C9(n≡0(mod2))也是成立的,并且给出了三种不同的优美标号.猜想对于任意正整数p是否成立,仍然是个公开问题.

二部得分表偶隐含k-强的充要条件

本文阐述了有向可图序列研究中一些没有解决的问题 ,给出了二部得分表偶S =[A ,B]隐含k -强的充要条件 ,解决了李炯生教授在数学进展中提出的部分问题 。

关于图的顶点性质的注记

本文首先推广了可到达顶点的概念,然后引进了V的子集的闭集和闭包的定义.最后得到一些有趣的性质和结果。

亏数为1的幂等变换生成半群的R~*-关系

令Singn为[n]={1,2,…,n}上的奇异变换半群.En-1为Singn中亏数为1的幂等变换的集合,对En-1的任意非空子集I,本文刻画其生成子半群S(I)满足关系式(α,β)∈R*Ker(α)=Ker(β),α,β∈S(I)的特征.

有向循环图与有向圈的乘积的研究

本文讨论了有向循环图与有向圈的乘积 ,得到了以下结果 :( 1)有向循环图D(n ;s1,s2 ,… ,si- 1,nl ,si+1,… ,sr)是连通的充要条件。( 2 )设有向循环图D(n ;s1,s2 ,… ,si- 1,s,si+1,… ,sr)连通 ,且n =ls,gcd(n ,s1,s2 ,si- 1,si+1,… ,sr) =l(l>2 ) ,则D(n ;s1,s2 ,si- 1,s,si+1,… ,sr) D(s ;s1l,s2l ,… ,si- 1l ,si+1l ,… ,srl)× μl。( 3)设D(n0 ;s1,s2 ,… ,sr)是连通 ,则D(n0 ;s1,s2 ,… ,sr)×μn1× μn2 ×… μns为有向循环图 gcd(ni,nt) =1(i,t =0 ,1,2 ,… ,s ;i≠t)。gcd(n ,s1,s2 ,… ,sr)表示n ,s1,s2 ,… ,sr 的最大公约数 ,μl

THE LINEAR ARBORICITY OF COMPOSITION GRAPHS

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.