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

有向全图的幂敛指数和周期

设G是有向图,T(G)表示G的有向全图.本文得到了它们的幂敛指数k(G)和k(T)之间的关系:对任何有向图G,周期p(T(G))=1;当G是本原图时,k(T)≤k(G)+1,文中给出了取得k(G)+1的两类图;当G是无圈图时,k(T)=2k(G)-1,当G是有向圈时,k(T)=2|V(G)|-1,当G是强连通时得到了k(T)的一些估计.     

有向图的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的一个有效算法.     

线有向图的幂敛指数

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

一类含有奇数个顶点的三色有向图本原指数上界

一个三色有向图D是本原的,当且仅当存在非负整数h、k和v,且h+k+v0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)-途径,h+k+v的最小值定义为三色有向图D的本原指数.研究了一类三色有向图,它的未着色图中包含2佗-4个顶点,一个n-圈、一个(n-2)-圈和一个2-圈,给出了本原指数上界.     

强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

关于直积n_1×n_2×…×n_k的哈密顿圈及哈密顿分解(英文)

设n1≤n2≤…≤nk是正整数，D=Cn1×Cn2×…Cnk。是有向圈的直积．在本文中，我们证明了如果ni|nk（1≤i≤k—1），则D含有哈密根图．当n1=n2＝…＝nk时，我们进一步得到D含有[k／2]个弧不交的哈密顿圈．作为副产品，我们推出当是哈密顿有向图时×也是哈密顿有向图．     

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

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

本原不可幂带号有向图的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)的若干上界,并提出了一个公开问题.     

围长为r的n阶本原有向图的点指数

研究本原有向图的顶点指数,运用图论与数论方法,得到了n阶围长为r的本原有向图的点指数expD（k）的上界：若rn,且r为素数,D∈Dn,r={D｜D为n阶本原有向图且围长为r},则expD（n,k）=rn-2r＋k（1≤k≤n）;若r｜n,且r为素数或素数的幂,D∈Dn,r,则expD（n,1）=rn-3r＋2.     

有向线图的限制性连通度

设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））．     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

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

一个有向多重图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)$含有生成迹.     

具有给定指数的本原有向图的Hamilton性质

本文解决了１９８２年Ｊ．Ａ．Ｒｏｓｓ提出的两个问题,并得到如下结果：（１）设Ｄ是具有围长ｓ＞１和指数γ（Ｄ）＝ｎ＋ｓ（ｎ－２）的ｎ阶本原有向图,则Ｄ是Ｈａｍｉｌｔｏｎ的;（２）设Ｄ是含有环的ｎ阶本原有向图且γ（Ｄ）＝２ｎ－２,则Ｄ是Ｈａｍｉｌｔｏｎ的当且仅当ｍａｘ｛ｄ（ｕ,ｖ）|γ（ｕ,ｖ）＝２ｎ－２｝＝ｎ－２．     

Ree群~2G_2(q)与2-(v,k,l)区组设计(Ⅱ)

本文证明了自同构群的基柱为Ree群~2G_2(q)的区-本原2-(v,k,1)设计必为Ree unital,即2-(q~3+1,q+1,1)设计,从而部分地回答了Praeger问题.     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.     

超欧拉扩展有向图

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.