广义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有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

2-控制数和连通2-控制数相等的图(英文)

任意一个图G =(V ,E) ,S是V(G)的子集 ,如果对每一个顶点u∈V-S都存在顶点v∈S ,使得d(u ,v) ≤ 2 ,则称S为G的一个 2 控制 .称最小的 2 控制集的顶点个数为G的 2 控制数 ,记为γ2 (G) .如果G的一个 2 控制集S的生成子集〈S〉是一个连通图 ,则称S为G的一个连通 2 控制集 .称最小的连通 2 控制集的顶点个数为G的连通 2 控制数 ,记为γc2 (G) .本文论述了树和单圈图中 2 控制数和连通 2 控制数相等的充分必要条件 .     

广义de Bruijn有向图的k-元控制集

G =(V,A)表示一个有向图,其中V和A4分别表示有向图G的点集和弧集.对集合Dk? V(G),如果对于任意点v ∈ V(G),都存在k个点ui,1≤i≤k(可能存在某个ui和v是同一点)使得(ui,v)∈ A(G),则称Dk是G的一个k-元控制集.有向图G的k-元控制数γxk(G)是G的最小k-元控制集所含点的数目...     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.     

强定向图的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-强直径的一个上界.     

单圈共轭图的最小广义Randic指标R-1

图G的广义Randic指标定义为Rα=Rα（G）=∑uv∈E（G）（d（u）d（v））^α,其中d（u）是G的顶点u的度,α是任意实数．本文确定了单圈共轭图的广义Randic指标R-1的严格下界,并刻划了达到最小R-1的极图,这类极图还是化学图．     

全有向图的幂敛指数

设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。我们还证明了以上界是不可改进的最好界。     

粘合运算对图的控制参数的影响

简单图G的粘合运算G_(uv)指的是重合G的两个顶点{u,v}并且去掉重边和环所得到简单图的运算．本文考虑了粘合运算对图的4个控制参数γ(G),Γ(G),β(G),i(G)的影响．刻画了图G_(uv)与图G的控制参数γ(G),Γ(G),γ(G),i(G)之间的关系．及给出γ(G_(uv))=γ(G)-1和β(G_(uv)=β(G)-1的充要条件．     

整数距离图G(Dm,k,2)的点线性荫度

整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集．本文讨论整数距离图的点线性荫度,记为vla(G(D))．对于m≥5k,设D_(m,k,2)={1,2,…,m}/{k,2k),得到vla(G(D_(m,1,2)))=■并决定出了G(D_(m,2,2))在某些特殊的仇值上点线性荫度的确切值以及当k≥3时G(D_(m,k,2))的点线性荫度的上、下界．     

图的符号星部分控制数

引入了图的符号星部分控制的概念.设G=(V,E)是一个简单连通图, M是V的一个子集.一个函数f:E→{-1,1}若满足∑e∈E(v)f(e)≥1对M中的每个顶点v都成立,则称f是图G的一个符号星部分控制函数,其中E(v)表示G中与v点相关连的边集.图G的符号星部分控制数定义为γM(85)(G)=min{∑e∈Ef(e)|f是G的符号星部分控制函数}.在本文中我们主要给出了一般图的符号星部分控制数的上界和下界,并确定了路、圈和完全图的符号星部分控制数的精确值.作为我们引入的这一新概念的一个应用,求出了完全图的符号星k控制数.     

扩展de Bruijn图的生成树和广播

扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为[log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.     

阶数极大的临界全控制图

称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γ_t, 则称这样的临界全控制图G 为γ_t- 临界的. 如果G 是γ_t- 临界的, 且阶数为n, 则n ≤ Δ(G)(γ_t(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γ_t = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γ_t(G)- 1) + 1 的3-γ_t- 临界图.     

本原对称有向图上广义指数的极图

设D是n阶有向图(允许有环但不允许有重复弧),X C V(D),集指数expD(X)是这样的最小正整数P,使得对D中每个点v,存在从X的至少一个点到V的长为P的途径.若这样的正整数P不存在,则定义expD(X)=∞.D的第k重上广义指数F(D,k):=max{expD(X)| X C V(D),|X|=k},1≤k≤n.如果F(D,k)<∞,则称D是k-上本原的.本文完全刻划了k-上本原对称有向图的第k重上广义指数的极图.     

不含4-圈与7-圈的平面图是(2,0,0)-可染的

设d1,d2,...,dk是k个非负整数.若图G=(V,E)的顶点集V可剖分成k个子集V1,V2,...,Vk使得对i=1,2,...,k,由Vi所导出的子图G[Vi]的最大度至多为di,则称G是(d1,d2,...,dk)-可染的.本文证明不含4-圈和7-圈的平面图是(2,0,0)-可染的.     

On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs

Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in- and outdegree d have arc-chromatic index 2d. In order to do this, we introduce the concept of even 1-factorizations. An even 1-factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1-factorization is a partition of the arcs into even 1-factors. We prove that if a digraph admits an even 1-factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1-factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc.     

对称有向图的广义本原指数集

一个有向图Ｄ称为本原有向图,若存在某自然数ｋ,使Ｄ中任一点ｕ到任一点ｖ都有长为ｋ之途径。若Ｄ是一个对称有向图,则Ｄ是本原的当且仅当Ｄ对应的无向图Ｇ连通且至少包含一个奇圈。本文研究最小奇圈长为ｒ的ｎ阶对称本原有向图,完全刻划了第一类广义本原指数集,并部分地解决了第三类广义本原指数集的刻划问题。