图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

图和有向图的测地数

对于图G（或者有向图D）内的任意两点u和υ,u-υ测地线是指在u和υ之间的最短路（或者从u到υ）.I（u,υ）表示位于一条u-υ测地线上所有点的集合,对于S（U∣）V（G）,I（S）表示所有I（u,υ）的并,这里u,υ∈S.图G（或者有向图D）的测地数g（G）（g（D））是使J（S）=V（G）（J（S）=V（D））的最小点集S的基数.定义G的所有定向图中测地数的最小值为G的下测地数,即g-（G）=min{g（D）：D是G的定向图）;定义G的所有定向图中测地数的最大值为G的上测地数,即g＋（G）=max{g（D）：D是G的定向图）.本文的主要目的是研究G V H 的上、下测地数,此外,文章给出了g（G）=g（G×P3）的一个充分必要条件.     

树的笛卡儿积的测地数

图G内的任意两点u和υ,u-υ测地线是指u和υ之间的最短路.I(u,υ)表示位于u一υ测地线上所有点的集合,对于子集S∈V(G),I(s)表示所有,(u,υ)的并,这里u,υ∈S.图G的测地数g(G)是使,I(s):V(G)的点集S的最小基数.本文研究了任意连通图G与树T笛卡儿积的测地数的界,同时,给出了任意两个树T1与T2笛卡儿积的测地数和树T与圈C笛卡儿积的测地数.     

图和有向图的测地数

图G内的任意两点u和v, u-v测地线是指u和v之间的最短路. I(u,v)表示 位于u-v测地线上所有点的集合, 对于子集SÍV(G), I(S)表示所有I(u,v)的并, 这里u,vÎ S. 图 G的测地数g(G)是使得I(S)=V(G)的点集S的最小基数. 对于有向图D, 类似地可定义g(D). 图G 的测地谱是G的所有定向图的测地数的集合, 记为S(G). G的下测地数g^-(G)=minS(G), 上测地数g⁺(G)=maxS(G). 文中主要研究了连通图G的g(G), g^-(G)和g⁺(G)之间的关系. 同时,还给出g(G)和g(G× K₂）相等的充分必要条件, 从而推广了 Chartrand, Harary 和 Zhang 的相关结论.     

图的笛卡儿积的测地数

对于图G内的任意两点u和v，u-v测地线是指u和v之间的最短路．I（u，v）表示位于u-v测地线上所有点的集合，对于．S∈V（G），I（S）表示所有I（u，v）的并，这里“u,v∈．S．G的测地数g（G）是使I（S）=V（G）的点集．S的最小基数．在这篇文章，我们研究G×K3的测地数和g（G）与g（G×K3）相等的充分必要条件，还给出了T×Km和Cn×Km的测地数，这里T是树．     

1-可嵌入曲面的图的边染色北大核心CSCD

一个图称为是1-可嵌入曲面的,当且仅当它可以画在一个曲面上,使得它的任何一条边最多交叉另外一条边.x′(G)和△(G)分别表示图G的边色数和最大度.给定图G是1-可嵌入到欧拉示性数x(∑)≥0的曲面∑上的图.如果△(G)≥8且不含4-圈或者△(G)≥7且围长g(G)≥4,则图G满足等式△(G)=x′(G),其中,g(G)表示图G中最短圈的长度.     

图Pn∨Km,n的全色数

对两个不交的图G,H,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv u∈V(G),v∈(H)},G∨H称为G和H的联图.本文得到了路Pn与完全二部图Km,n的联图Pn∨Km,n的全色数.     

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

几类图弱控制的广义束缚数

对任一图G,其弱控制的束缚数,广义束缚数分别定义为bw(G)=min{|E‖E(∪)E(G),且γw(G-E)＞γω(G)}.b'ω(G)=min{t|(A)E(∪)E(G),如果|E|=t,则有γω(G-E)＞γw(G)}.在本文中我们给出了几类图的弱控制的广义束缚数的精确值,称b'ω(G)=1图为弱控制去边临界图,并研究了正则图是弱控制去边临界图的充要条件,以及一般图和树的必要条件.     

关于Menger图和Menger数的若干结果

该文研究Menger图和Menger数. 主要结果如下 : (1)\ 对任意的n≥4, n立方体Q\-n不是Menger图. 解决了Sampathkumar提出的未解问题2. (2)\ 如果G是一个偶图, 则m(G)=β\-0(G),其中m(G)是G的Menger数, β\-0(G)是G的独立数. 部分解决了Sampathkumar提出的未解问题3. (3)\ “确定图的Menger数”问题是NP困难的.     

The lower and upper forcing geodetic numbers of block–cactus graphs

A vertex set D in graph G is called a geodetic set if all vertices of G are lying on some shortest u–v path of G, where u, v ∈ D. The geodetic number of a graph G is the minimum cardinality among all geodetic sets. A subset S of a geodetic set D is called a forcing subset of D if D is the unique geodetic set containing S. The forcing geodetic number of D is the minimum cardinality of a forcing subset of D, and the lower and the upper forcing geodetic numbers of a graph G are the minimum and the maximum forcing geodetic numbers, respectively, among all minimum geodetic sets of G. In this paper, we find out the lower and the upper forcing geodetic numbers of block–cactus graphs.     

剖分Petersen图得到的新测地块

通过剖分Petersen图我们得到了一类新的测地块．由此成功构造了给定直径为6和围长为11的测地块，解决了近二十年来悬而未决的一个存在性和构造性问题．     

一种新的测地块的构造

本文给出了一种新的测地块的构造方法，这种方法不同于已有的所有方法，它是由ＢＤ设计和某些已知的测地块来构造的。同时肯定地回答了Ｐｌｅｓｎｉｋ提出是否存在不同于ＷＰｄ和Ｋｎ＾（ｉ）的测地块的问题。     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

具有唯一完美匹配的D-图

为了研究具有完美匹配图的Tuttc集和极端集,文献[1,2]提出了一种新的图运算,并且得到了许多有趣的性质。本文中,我们刻画了level（G）=0的具有唯一完美匹配的饱和图G,并且确定了具有唯一完美匹配图的D-图的边数的紧上界。     

4p阶二面体群连通3度Cayley有向图的正规性

设G是一个有限群,S是G的不包含单位元1的非空子集,定义群G关于S的Cayley(有向)图X:=Cay(G,S)如下:V(X)=G,E(X)={(g,sg)|g∈G,s∈S}.Cayley(有向)图X:=Cay(G,S)称为正规的,如果G的右正则表示R(G)在X的自同构群Aut(X)中是正规的.设G是4p阶二面体群(p为素数).考察了Cay(G,S)连通3度的正规性,并给出了这些图的全自同构群.     

Q整图新类

对于一个简单图G, 方阵Q(G)=D(G)+A(G)称为G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别为G的度对角矩阵和邻接矩阵. 一个图是Q整图是指该图的无符号拉普拉斯矩阵的特征值全部为整数.首先通过Stanic 得到的六个顶点数目较小的Q整图,构造出了六类具有无穷多个的非正则的Q整图. 进而,通过图的笛卡尔积运算得到了很多的Q整图类. 最后, 得到了一些正则的Q整图.