有向图反能量的一个注记

有向图的反能量是指有向图的反邻接矩阵的能量.本文利用有向图的运算构造出了几类有向图,它们中的每一个都满足有向图的反能量等于其底图的能量.部分回答了Adiga等人在文[The skew energy of a digraph,Linear Algebra Appl.,2010,432:1825-1835]中提出的一个公开问题.     

有向图字典乘积的代数群性质

字典乘积有向图G_1→⊙G_2是通过已知阶数较小的有向图G_1和G_2构造来的,这些小有向图G_1和G_2的拓扑结构和性质肯定影响大有向图G_1→⊙G_2的拓扑结构和性质.运用群论方法,证明了有向图字典乘积的一些代数性质,如:结合律、分配律等.     

有向图覆盖的Zeta函数

Mizuno和Sato定义了有向图的Zeta函数(见Linear Algebra Appl.,2001,336:181-190),它可用来计算有向图中具有给定长度的所有圈的个数.给出了任意有向图的覆盖的Zeta函数的计算公式.作为推论,覆叠重数为2,3和4的任意有向图覆盖(正则或非正则)的Zeta函数被计算出来,同时也计算了Cayley有向图的Zeta函数.     

正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

依赖团数的有向图极大弧连通的充分条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)=δ(D)时,称有向图D是极大弧连通的.本文给出了依赖团数的有向图极大弧连通的一些充分条件.     

依赖团数的有向图极大与超级边连通的度序列条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.给出了依赖团数的有向图极大和超级边连通的度序列条件.     

有向图及其道路同调的△集刻画

近几年来,A.Grigor'yan,Y.Lin,Y.Muranov,V.Vershinin和S.T.Yau等人研究了有向图上的道路,定义了有向图的道路同调并将其作为重要的代数工具来研究有向图的拓扑结构.将有向图上的道路集合描述为△集的分次子集,通过推广超图的嵌入同调定义△集的分次子集的嵌入同调并证明有向图的道路同调可以描述为△集的分次子集的嵌入同调.     

分支数≤7时S^2NS有向图的禁用子图刻划

实方阵A称为强符号非异阵（S~2NS阵）,若任一与A符号模式相同的矩阵非异且其逆的符号模式也一致。若一个有向图是某一S~2NS阵对应赋号有向图的基础有向图,称为S~2NS有向图。本文用禁用子图形式给出了分支数≤7时有向图成为S~2NS有向图的刻划,同时部分地解决了[2]和[4]中提出的问题。     

本原不可幂带号有向图的lewin数的界

如果存在正整数k使得对于D中任意两点u和v(允许u=v),在D中都有从u到v的长为k的有向途径,则称有向图D是本原的.给有向图的每条弧赋以符号+1或者-1得到的图S称为带号有向图.如果带号有向图S中包含SSSD途径对,即包含两条有相同的起点,相同的终点,相同的长度,并且有不同的符号的途径对,则称S是不可幂的.在本文中,我们将Lewin M提出的lewin数的概念从本原有向图推广到本原不可幂带号有向图,给出了本原不可幂带号有向图S的lewin数l(S)的若干上界,并提出了一个公开问题.     

矩阵对角相似的图论判别法

本文证明了任意两个ｎ阶复矩阵Ａ和Ｂ为对角相似的充要条件是：它们有相同的伴随有向图，并且以此有向图为基础有向图，以Ａ和Ｂ的对应非零元素比值为弧权值的赋权有向图满足“无向圈平衡条件”。我们还给出了矩阵对角相似条件在非负矩阵谱理论研究中的一个应用。     

k-Walk-Regular Digraphs

In this paper,we define a class of strongly connected digraph,called the k-walk- regular digraph,study some properties of it,provide its some algebraic characterization and point out that the 0-walk-regular digraph is the same as the walk-regular digraph discussed by Liu and Lin in 2010 and the D-walk-regular digraph is identical with the weakly distance-regular digraph defined by Comellas et al in 2004.     

超欧拉扩展有向图

A digraph D is supereulerian if D has a spanning eulerian subdigraph. BangJensen and Thomass′e conjectured that if the arc-strong connectivity λ(D) of a digraph D is not less than the independence number α(D), then D is supereulerian. In this paper, we prove that if D is an extended cycle, an extended hamiltonian digraph, an arc-locally semicomplete digraph, an extended arc-locally semicomplete digraph, an extension of two kinds of eulerian digraph, a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfyingλ(D) ≥α(D), then D is supereulerian.     

A Characterization of Locally Semicomplete CKI-digraphs

A digraph is locally-in semicomplete if for every vertex of D its in-neighborhood induces a semicomplete digraph and it is locally semicomplete if for every vertex of D the in-neighborhood and the out-neighborhood induces a semicomplete digraph. The locally semicomplete digraphs where characterized in 1997 by Bang-Jensen et al. and in 1998 Bang-Jensen and Gutin posed the problem if finding a kernel in a locally-in semicomplete digraph is polynomial or not. A kernel of a digraph is a set of vertices, which is independent and absorbent. A digraph D such that every proper induced subdigraph of D has a kernel is said to be critical kernel imperfect digraph (CKI-digraph) if the digraph D does not have a kernel. A digraph without an induced CKI-digraph as a subdigraph does have a kernel. We characterize the locally semicomplete digraphs, which are CKI. As a consequence of this characterization we conclude that determinate whether a locally semicomplete digraph is a CKI-digraph or not, is polynomial.     

DIGRAPH CATEGORIES AND LINE DIGRAPH FUNCTORS

The authors define line digraph functors on digraph category which are full and faith-ful and,as a consequence of the result,determine all homomorphisms in De Bruijn-Goodgraph category and automorphisms of Kautz digraph category.Moreover the authorsconsider a type of arc-full morphisms of digraph category such that F~n(f) is arc-full foreach functor F~n,and succeeding paper [9] study the strong homomorphisms of de Bruijn-Good digraph.     

Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size

Let D be a finite and simple digraph with vertex set V (D). The minimum degree δ of a digraph D is defined as the minimum value of its out-degrees and its in-degrees. If D is a digraph with minimum degree δ and edge-connectivity λ, then λ ≤ δ. A digraph is maximally edge-connected if λ=δ. A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree. In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.     

Connection digraphs and second-order line digraphs

The primary result of this paper gives a set of necessary and sufficient conditions for a digraph to be second-order line digraph of some digraph. A directed analogue of the concept of an intersection graph, defined for collections of ordered pairs of sets and called the connection digraph, is used to achieve this result.     

有向图n·_3优美的进一步性质

本文在我们以往研究基础上 ,得到了有向图 n· C 3优美的进一步性质 :两个无交有向图 n· C 3各自的公共顶点与一个新增加的顶点 ,分别用有向弧来连接 ,使该新增加顶点的出度为 2或入度为 2时 ,这样连接而得的有向图为优美图     

有向圈的行列式算法及HAMILTON图条件

本文引入有向路乘法、弧行列式等概念 ,讨论了弧行列式的性质 ,阐述了二种计算有向圈的行列式方法及有向图 D为 Hamilton图的充要条件 ,最后给出了计算实例     

New Extensions of Kernel Perfect Digraphs to Kernel Imperfect Critical Digraphs

In this paper we develop a general method to extend a kernel-perfect digraph to a critical kernel-imperfect digraph.