超欧拉扩展有向图

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.     

线有向图的幂敛指数

设G是有向图，LG表示c的线有向图，本文得到了它们的幂敛指数及周期之间的关系：k（G）－1≤（LG）≤k（G）＋1,p（LG）=p（G）特别地，当G为本原图时有：k（LG）＝k（G）＋1     

关于超空间连通性的一个注记

本文回答了由E.Klein与A.C.Thompson在其著作《Thery of Correspondences》中提出的一个问题。主要结果是:若X是一度量空间,且在X中存在一条弧,则在P(X)中有一条序弧α,满足条件i)α(0)是连通子集;ii) (?)α(t)是不连通的。     

关于循环有向图的强连通度

本文定义的循环有向图D(n;S)在分布式环形计算机互连网络设计中被广泛运用。本文证明了D(n;S)的强连通度k>2/3|S|。     

线有向图的幂敛指数

采用有向图的矩阵表示,得到了线有向图的幂敛指数和周期的有关结果.     

一类3度正则有向图网络模型

讨论了一种3度正则网络，这类网络具有较小的网络直径，本给出了网络直径、网络支撑树和欧拉环游的数目的公式．     

关于有向图的Euler线

有向图的Euler线是个古老的问题，本给出了一个有向图存在Euler线的一组充要条件。     

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

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

全有向图的幂敛指数

设D为有向图，T（D）为D的全有向图（Total-digraph),k(D)和p(D)分别为D的幂敛指数（Index of convergence)与周期（Period)，本文证明了。1，对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2K(D) 1}，特别地，当D为本原有向图时，k(T(D))≤k(D) 1，当D不含有向圈时，k(T(D))=2k(D)-1；当D为有向圈Cn时，k(T(D))=2n-1.2。对任意非平凡强连通图D,k(T(D))≥Diam(D) 1。我们还证明了以上界是不可改进的最好界。     

有向图和弱正则有向图补图的特征多项式的计算方法

本文解决了一般有向图的特征多项式的图论计算方法,并且给出了弱正则有向图和它的补图之间特征多项式的关系,从而也就解决了非负整数方阵特征多项式的图论计算方法问题。     

广义de Bruijn有向图及其叠线图的支撑树与欧拉环游的计数

给出了一类特殊的广义deBruijn有向图的支撑树与欧环游的数目的简洁表示式，并得到了广义deBruijn有向叠线图的支撑树与欧拉环境数目的计算公式。     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

A Note on the Order of Iterated Line Digraphs

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices of the k‐iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of G.     

广义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))= .     

有向线图的限制性连通度

设D=（y（D）,A（D））是一个强连通有向图．弧集S A（D）称为D的k-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于后．最小k-限制性弧割的基数称为k-限制性弧连通度,记作Ak（D）．k-限制性点连通度Kk（D）可以类似地定义．有k-限制性弧割（k-限制性点割）的有向图称为λk-连通（kk-连通）有向图．本文研究有向图D的限制性弧连通度和其线图L（D）的限制性点连通度的关系,证明了对任意λk-连通有向图D,kk（L（D））≤λk（D）,当k=2,3时等式成立;若L（D）是Kk（k-1）连通的,则λk（D）≤Kk（k-1）（L（D））;特别地,若D是一个定向图且L（D）是Kk（k-1）／2．连通的,贝0Ak（D）≤Kk（k-1）,2（L（D））．     

有向跳图的生成欧拉子有向图

一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.     

Perfect matchings of a graph associated with a binary de Bruijn digraph

Let B_n be the binary de Bruijn digraph of order n and W the quotient set of the set of vertices of B_n with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that (v,u) is an arc of B_n. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.     

有向图的L(j,k)数的上界

给定正整数j≥k,有向图D的一个L(j,k)-标号是指从V(D)到非负整数集的一个函数f,使得当x在D中邻接到y时|f(x)-f(y)|≥j,当x在D中到y距离为二时|f(x)-f(y)|≥k.f的像元素称为标号.L(j,k)一标号问题就是确定(?)j,k-数(?)j,k(D),这个参数等于(?) max{f(x)|x∈V(D)},这里f取遍D的所有L(j,k)-标号.本文根据有向图的有向着色数及最长有向路的长度来研究(?)j,k-数,证明了:(1)对任何有向着色数为(?)(D)的有向图D,(?)j,k(D)≤((?)(D)-1)j;(2)对任何最长有向路的长度为l的有向图D,如果不含有向圈或者D中最长有向圈长度为l 1,则(?)j,k(D)≤lj.并且这两个界都是可达的.最后我们对l=3的有向图给出了3j-L(j,k)-labelling的一个有效算法.