局部内(外)半完全有向图可迹的充分条件

本文利用多重插入法,对局部内(外)半完全有向图及其扩张有向图的可迹性作了讨论.首先,证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}满足d(x)≥n-1,d(可)≥n-2,或d(x)≥n-2,d(y)≥n-1,则D是可迹的.同时还证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}有min{d~+(x)+d~-(y),d~-(x)+d~+(y)}≥n-1,D是可迹的.其次,证明了n阶连通的扩张局部内半完全有向图D,如果任意不相邻的控制点对{u,v}和任意不相邻的受控点对{x,y}同时满足(1)d(u)≥n-1,d(v)≥n-1;(2)d(x)≥n-1,d(y)≥n-2或d(x)≥n-2,d(y)≥n-1,则D是可迹的.最后,利用逆图的性质把这三个结论推广到n阶连通的局部外半完全有向图与n阶连通的扩张局部外半完全有向图中.     

有向图的谱半径的二次度形式的上界

1 预备知识设D=D(V,E)为n 阶有向图(V 为顶点集,E 为弧集),其邻接矩阵A=A(D)= (α_(uv))_(n×n)的所有特征根:λ_1,λ2,…,λ_n 被称为有向图D 的邻接谱,简称谱.称(?){|λ_i|} 为D 的谱半径,记作ρ,ρ(D)或ρ(A).用d~-(u)和d~ (u)分别表示D 中顶点u 的入度和出度. 记V~-(u)={v}(v,u)∈E},V (u)={v|(u,v)∈E}.m~-(u)=1/((d~(u))(?)d~-(v), 称为D 中顶点u 的平均二次入度,m~ (u)=1/((d (u))(?)d~ (v),称为顶点u 的平均二次出度.其它有关术语可参考[1,2].     

一类极小本原对称图的指数集

运用有向图方法完全确定出顶点带环的n阶极小本原对称有向图的本原指数集,所得的结论是:1)顶点全部自带环的n阶极小本原对称有向图所成的子图类之本原指数集E1={2,3,…,n-1};2)顶点不全带环的n阶极小本原对称有向图所成的子图类之本原指数集E2={2,3,…,2n-2}\S,其中S是{n,n+1,…,2n-2}中的所有奇数之集;3)顶点带环的n阶极小本原对称有向图所成的特殊图类之本原指数集En=E1∪E2={2,3,…,2n-2}\S.     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.     

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

一个三色有向图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-圈,给出了本原指数上界.     

极小强连通本原有向图的本原指数集

本文的主要结果为:(1)当一个n阶极小强连通本原有向图至少含三个不同圈长时,有γ(D)≤[1/2(n~2-6n+14)](当n≥14时)。(2)e(n)≥[1/2(n~2-6n+16)],即从6到[1/2(n~2-6n+14)]的所有正整数都是某个n阶极小强连通本原有向图的本原指数。(3)给出了n阶极小强连通本原有向图的本原指数集NE_n的明确表达式。     

围长为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个正对角元,且本原指标为2n—d—1的n阶本原矩阵的存在性,记M={A|A含d个正对角元,且γ(A)=2n-d-1}又设N(A)是A中含正元的个数,我们证明了N(A)=minN(B)的充要条件是A同构于D     

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

连通图中过指定顶点集的圈的存在性

图论中的一个重要问题是Hamilton圈的存在性问题.由于一般的Hamilton图的充要条件难于获得,故一些作者便退一步在某些给定类型的图中寻求长度尽可能大的圈.例如,Dirac即证明了2-连通图中存在着经过某一指定顶点集N(u)UN(v)U{u,v}的圈,从而得到了如下的定理(可参看[3]的介绍): 定理A.设G是个n阶的2-连通图,P是G中的一条最长路,u及v是P的两端点,d(u)+d(v)=f.若4≤f相似文献