Harary定理的一个简短证明

关于所有(p,q)图的极大连通度,Harary找出了一个定理.本文给出这个定理的简短证明;方法是首先借助于数论中的一个引理,然后构作出两个图形以取代Harary图族中的两个;证明是用反证法给出的.     

直径稳定图和边直径稳定度

一个图 G 称为是一个(l,d)——稳定图(关于边的),如果对于 G 的边集 E(G)的任意一个子集 E,只要满足 E 中的边数≤l-1,都有图 V-E 的直径 d(V-E)≤d。(这里 l,d 都是正整数)。如果更有G 的直径 d(G)=d,则称 G 为 l 直径稳定图。一个图 G 的边直径稳定度(line-persistence)ρ_1(G)是为了要使得在 G 中去掉一些边后所得到的图 G′的直径 d(G′)>d(G)或者使 G′不连通所必须去掉的最少边数。(l,d)——稳定图和 l 直径稳定图的概念是首先由 J.Hartman 和 I.Rubin 于1956年在[1]中提出的。直径稳定度的概念是由 F.T.Boesch;F.Harary 和 J.A.Kabell 于1981年在[2]中首先提出的。本文对直径稳定图和边直径稳定度作了进一步的考察,得到了一些关于直径稳定图的结论,并初步讨论了直径稳定图和边直径稳定度之间的关系,最后,通过一个引理和一个推论给出了几个 l 直径稳定图族,从而解决了 Hartman 和 Rubin 在[1]中提出的两个问题,同时所给出的图族证明了 Boesch;Harary 和 Kabell 在[2]中所给出的一个关于边直径稳定度的“定理”是不正确的。(注:此“定理”有两种“等价”的叙述方法,本文所给出的图可作为这两种叙述的反例。)     

上准正则(p、δ、k)图存在的必要充分条件

本文采用[1]或[2]的术语和记号.称最小度为δ且连通度为k的p阶简单图为(p,δ,k)图,称最小度为δ且棱数为q,?的p阶简单图为δ度上准正则图,其度为δ 1的顶点称为上奇点.图H_(p,δ,k)表示上准正则(p,δ,k)图,G=H_(p,δ,k)表示G是图H_(p,δ,k).Harary曾就p>δ=k≥2作出图H_(p,δ,k).今用图H_(p,δ)记这类图,并用图H_(p,0)记p阶空图,图H_(p,1)记p阶1度上准正则图.     

kp,q（G）≤λp,p（G）成立的一些充分条件

设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用λp,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1.p-连通图的一些性质.     

五面体平图中的生成树的构造与计数

首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系S(G)=C(G)+T(G);其次对于任意连通图,以p=4,q=6的完全图K4为例给出了生成子图个数的计算公式,同样以p=4,q=6完全图K4为例给出了生成树的构造定理和计数定理,提出了图S(G)生成树的计数方法和构造方法;最后,介绍了五面体平图生成子图个数的计算和各生成子图的构造,并验证了所给公式的正确性,从而解决了任意平图G(p,q)生成树的构造问题。     

外部平面图的L(p,q)-标号

对于正整数p,q,n与图G,如果函数φ:V(G)→｛0,1,2, ,n｝满足如下关系:若distG(u,v)=1,则|φ(u)-φ(v)|≥p;若distG(u,v)=2则|φ(u)-φ(v)|≥q,那么称函数φ为图G的L(p,q) 标号.在所有L(p,q) 标号中最小的n称为(p,q) 跨度,记作λ(G;p,q).本文证明了如下结论:设图G是一个最大度为Δ的外部平面图,那么λ(G;p,q)≤qΔ+4p+2q-4.     

高度平面图的L(p,q)—标号

研究高度平面图G的L(p,q)-标号问题，证明了高度平面图h1-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+6(p-q)；h2-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+8p-6q-1. 对于L(2,1)标号问题Griggs和Yeh有一著名猜想：对最大度为Δ的任意图有λ(G)Δ2. 此猜想对高度平面图是正确的.     

根图的稳定性及其优化

设灾难发生时,根图G的边以概率p独立幸存,则含根连通子图的顶点数的期望值EV(G;p)是根图的可靠性的合适指标.定义了子图的顶点数的平方期望值E2(G;p)后,则方差D(G;p)=E2(G;p)-[EV(G;p)]~2是根图稳定性的合适指标.推导得到了E2(G;p)的减-缩边公式,从而得到方差的一个递归计算方法.进而研究了一些特殊图的方差的计算公式.最后,结合期望和方差,讨论了根图的优化问题.     

Halin图的列表L(p,q)标号

图G的一个列表L,是指对G的每一个顶点v指定的一个标号集合L(v)。G的一个列表L(p,q)-标号是G的一个正常L(p,q)-标号,使得每一个顶点v∈V(G)均可在其对应的列表L(v)里选取一个标号。G的一个k-列表L(p,q)标号是一个列表L(p,q)-标号,使得G的所有顶点v的列表L(v)的长度L(v)=k 1。定义G的列表L(p,q)-标号数λl(G)=m in{G k有一个k-列表L(p,q)-标号}。讨论了Halin图的列表L(p,q)-标号问题,证明了λl(G;p,q)≤(2q-1)Δ(G) 6p-3。     

(K1,4;2)-图的闭包

定义一个新的图类(K1,p;q)-图(p≥3,q≥1),它是无爪图的推广.证明了(K1,p;q)-图的一个重要性质;(K1,p;q)-图必为(K1,p 1;q 1)-图,并给出了以下结论:设G是T3-free或K1∨P4-free的(K1,4;2)-图,则1)cl(G)仍为(K1,4;2)-图;2)cl(G)是唯一确定的.     

高度平面图的列表L(p,q)-标号

如果平面图G的最大度Δ(G)=|V(G)|-k, k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.研究了高度平面图G的列表L(p,q)-标号问题, 给出了高度平面图G的列表L(p,q)-标号数λl(G;p,q)的上界,并对h1-图证明了λl(G;p,q)≤(2q-1)Δ 6(p-q);对h2-图有λl(G;p,q)≤(2q-1)Δ 8p-6q-1.     

一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

简单图的生成树数的进一步探讨

利用Cayley公式求解递推关系方程,给出了一组简单图S（p,n,p）,S（p,n,q）的生成树数的计算公式.     

图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

连通图的Harary指数上界及其极图

图的Harary指数定义为图的所有顶点对的距离的倒数之和.刻画了在给定点数和直径的图类中,Harary指数达到最大的极图,并由此确定了Harary指数关于直径的一个上界.另外,在n阶连通图中,刻画了Harary指数达到第二大和第三大的图的结构.     

完备三分图的同构分解

图G=(V,E)的边集E的一个分划{E~1,…,E~j}叫做G的一个同构分解,如果 (ii) E~j的边导出子图G~j=(V,E~j)彼此同构。G~1,…,G~j叫做G的一组同构因子,如果H≌H~j(≌表示同构),称H可分G,记为H|G。如果G的一组同构因子恰好有t个子图,称G是t可分的,或t可分G,记为t|G。如果|E|=q,t|G的一个明显的必要条件是t整除q、记为t|q。 F.Harary,R.W.Robinson和N.C.Wormald对于完备三分图K(m,n,s),当     

两个完全图的匹配和的L(p,q)-标号

设p,q为两个非负整数,一个图G的L(p,q)-标号是一个从G的顶点集V(G)到一个非负整数集的映射f,使得对于G中的任意两个顶点u,v,当d(u,v)=1时,|f(u)-f(v)|≥p;当d(u,v)=2时,|f(u)-f(v)|≥q;根据p,q之间的关系,给出两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的上界.而当q≤p≤2q时,确定了两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的准确值.     

欧拉跳跃图

讨论欧拉跳跃图,给出一个图是欧拉图,其跳跃图J(G)是欧拉图的充要条件及一个连通图G=(p,q)的跳跃图J(G)是欧拉图的充要条件,即定理1:设G=(p,q)是欧拉图,则J(G)是欧拉图当且仅当q≥5为奇数.定理2:设G=(p,q)是连通图,则J(G)是欧拉图的充要条件是⑴q≥5是奇数且q>ζ 1,每点的度有相同的奇偶性;⑵q≥6是偶数且q>ζ 1,任意一边的两端点的度有相异的奇偶性.其中ζ=max{d|u| d(v)|uv∈E(G)}.     

完备三分图K(A,B,C)有同构因子的某些充分条件

如果图G(V,E)可以分解成t个彼此同构的边不重子图的并,则称G有t个同构因子,或者说t可分G,记为t|G。若G有q条边,t|G的一个明显的必要条件是f|q,并称之为可分性条件。 Harary,Robinson和Wormald证明了对于完备三分图当t=2,4时可分性条件是充分的,且猜测t为偶数时,可分性条件是充分的。本文证明了t=2~k时,这个猜测成立。摘     

三路树P（2m,2m,2m）是边幻图的证明

令简单图G－（V,E）是有p个顶点q条边的图,假设G的顶点和边由1,2,3,,…,p q所标号,且f:VUE→{1,2,…,p q}是一个双射,如果对所有的边xy,f(x) f(y) f(xy)是常量,则称图G是边幻图（edge-magic),文[1]中猜测树是边幻图,本文证明了三路树P（m,n,t）当m,n,t为偶数且相等时为边幻图。