直径为n-2的图的最小特征值

对于一个图的集合Ψ,若图G是Ψ中所有图的最小特征值达到最小的那个图,则称G是集合Ψ中最小特征值的极小图.文章刻画了直径为n-2的n阶连通图最小特征值及其极小图.     

连通图和不连通图的维纳指数W（G）

一个连通图的维纳指数W(G)等于图中所有无序点对的距离之和。本文研究了连通图和不连通图的维纳指数W(G),得到了上界图;以及研究了W(G) W(G)的上界和下界。     

直径粘接图的pebbling数

图G的pebbling数f(G)是指在一个图G的顶点上以任意方式放置若干个pebble数目的最小值,满足通过一系列的pebbling移动使得任一指定目标顶点能得到一个pebble,而pebbling移动是从一个顶点处移走两个pebble并把其中的一个移到与其相邻的一个顶点上.文章定义了将两个图的直径端点之一粘接生成的一类粘接图,主要计算了一些粘接图的pebbling数,发现了两类满足pebbling数直径下界的图.     

关于直径为2-临界图的Murty-Simon猜想

称图G是直径为2-临界图,如果G的直径是2,任意删掉一条边这个图的直径都会增加.一个非常著名的猜想,称为Murty-Simon猜想,指出对于任意有n个点的直径为2-临界图,它的边数最多为[n2/4」,且为完全二部图K[n/2],[n/2]时可以取到边数的上界.一个图称为是3t-临界图,简记为3tEC,如果它的全控制数是...     

关于p阶临界2边连通图的一个注记

在文[1-2]分别给出了p阶临界2边连通图最大边数及其结构图的基础上给出了p阶临界2边连通图最大边数相应结果。     

图的最大亏格与直径

设G是直径为4的简单图,若G不含3阶完全子图K3,则G的Betti亏数ξ(G)≤2,即G的最大亏格γM(G)≥1/2β(G)-1,并且不等式的下界是可达的。这种结合图的直径等条件的证明方法改进了相关结果。     

行数为2的变换图的直径和距离性质

著名的图论专家Richard A.Brualdi于1980年提出了关于变换图G(R,S)直径的Brualdi猜想,但至今仍悬而未决。变换图的距离性质已在组合矩阵论、网络流理论等领域中得到了广泛的应用。基于对行数为2的变换图G(R*,S*)的基础结构性质的研究,得出变换图的距离和结构性质,G(R*,S*)的直径为r,对于G(R*,S*)中任意两个距离为k的点,存在k²条内部不交的最短路联结这两个点。     

可连通图序列的一个连通图实现的构造算法

给出了一个从可连通图序列构造一个连通图实现的算法并证明了该算法的正确性。     

大直径等径弯管展开图的解析画法

结合现场实际问题，具有针对性的总结归纳出了解析法作图的具体方法和步骤，并在理论上加以验证，使大直径弯管展开图的画法更简便易行。     

On 3-diameter-stable graphs of diameter 4

In this paper we give a necessary and sufficient condition for a graph G with diameter 4 to be 3-diameter-stable.This result extended some known results.     

关于直径为5的图脆弱度的一个注记(Ⅱ)

The line persistence of a graph G, p1 (G) is the minimum number of lines which must be removed to increase the diameter of G. In Ref. [ 7 ] ( J. Shanghai Univ., 2003,7(4) :352-357), we gave a characterization of graphs of diameter five with P1 ( G ) ≥ 2. In this paper we will show that each of the 8 special graphs Xi ( i = 1,2,3,4,5,6,7,8 ) listed in condition (2) of Theorem 1 in Ref. [ 7 ] can not be deleted. Therefore the results we obtained in Ref. [ 7 ] can not in general be improved.     

A Note on Vulnerability in Graphs of Diameter Five （ Ⅱ ）

The line persistence of a graph G, Pt （ G ） is the minimum number of lines which must be removed to increase the diameter of G. In Ref. [7] （J. Shanghai Univ., 2003,7（4）：352-357）, we gave a characterization of graphs of diameter five with ρ1 （ G ）≥2. In this paper we will show that each of the 8 special graphs Xi （ i = 1,2,3,4,5,6,7,8） listed in condition （2） of Theorem 1 in Ref. [7] can not be deleted. Therefore the results we obtained in Ref. [7] can not in general be improved.     

A Note on Vulnerability in Graphs of Diameter Five(Ⅱ)

1IntroductionIn general,we followthe notation and terminologyin Refs.[1-5,7].In this paper all graphs are si mple.LetGbe a graph,V(G)the vertex set ofG,andE(G)the edge set ofG.The distance between twoverticesx,y∈V(G)is denoted bydG(x,y).Thediameter ofGis denoted byd(G).A short(x,y)-pathis an(x,y)-path with length≤d(G).An edgee∈E(G)is called cyclic if there exists a cycle inGcontaininge.To each cyclic edgee,letg(e)be thelength of the shortest cycle containinge.Ifeis abridge theng(e)…     

Results on diameter-stable graphs related to girth

A graph G is said to be an （l,d）-graph （with respect to edges） if d（G-E）≤d,E E（G） such that ｜ E ｜≤l-1.The l-diameter-stable graphs are （l,d）-graphs with diameter d.In this paper some new results on diameter-stable graphs are obtained.     

关于距离图的L(2,1)-标号着色

研究了距离图G(D)的L(2,1)-标号色数λ(D).证明了距离图满足λ(G)≤Δ2.对于任意给定的正整数k,证明了λ({1,2,..., k})＝2k 2和λ({1,3...,2k-1})＝2k 2.假设k,a∈N且k,a≥2.如果k≥a,则λ({a,a 1,...,a k-1})＝2(a k-1).否则,λ({a,a 1,...,a k-1})≤min{2(a k-1),6k-2}.若D由2个正整数构成,则6≤λ(D)≤8.对于特殊的距离集D＝{k,k 1}( k∈N),λ(D)的上界改进到了7.     

树和乘积图的圆L（j,k）-标号数（英文）

设j,k和m是3个正整数.给定一个图G.设f：V（G）→{0,1,…,m-1}是一个映射.如果对图G的任意一对相邻顶点u和v都有f（u）-f（v）m≥j,对任意一对距离为二的顶点都有f（u）-f（v）m≥k,其中a-bm=min{a-b,m-a-b},则称f是图G的一个圆m-L（j,k）-标号.使得图G有圆m-L（j,k）-标号的最小的正整数m称为图G的圆L（j,k）-标号数,记为σj,k（G）.对任意2个满足j≤k的正整数,确定了树以及2个完全图的笛卡尔乘积图和直积图的圆L（j,k）-标号数.     

解析几何创建史

解析几何是一门划时代的数学,它彻底改变了数学的研究方法,将初等数学嬗变为高等数学,为数学科学搭建了赖以繁衍生息的大厦的框架。笛卡儿的《几何学》建立了平面坐标系,将平面上点和实数对(x,y)建立了一一对应关系,是代数与几何第一次完美结合,开创了数学学科的崭新时代。笛卡儿被公认为解析几何的创始人。     

具有最少可能边数的唯一k-可染色图的构造

Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this note, we construct-an infinite familyof uniquely vertex k-colorable graphs of the order n, the size n（k - 1） - （^k2） and the minimum degree k by using a recursion method.     

图的L(d,1)-标号的边跨度

对于给定图G顶点集上一个非负整数函数f,满足:若dG(u,v)＝1,f(u)-f(v)≥d;若 dG(u,v)＝2,f(u)-f(v)≥1.称f 为L(2,1)-标号.这是由频道分配问题抽象出来的数学模型.本文主要研究该标号问题的一个参数,即边跨度,记作βd(G)＝minf max{f(u)-f(v):u∈V(G)},即对于所有正常的L(d,1)-标号,使得相邻顶点标号之差的最大值达到最小.本文主要讨论了圈Cn、树T、 k-部完全图、正三角形网格、 正四边形网格以及弦图等图类的边跨度,并给出了确切的数值.