图的{P_4}—分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}—分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}—分解.     

双圈连通图的L(2,1)-labelling

给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,f(u)-f(v)≥2;当dG(u,v)=2时,f(u)-f(v)≥1.如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)-labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.     

图的L(3,2,1)-标号

无向图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z*的一个映射,满足:对i=1,2,3,只要dG(x,y)=i,则f(x)-f(y)|≥4-i.若一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为k-L(3,2,1)-标号.图G的L(3,2,1)-标号数,记作3λ(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.文中给出了路、圈、树等特殊图的L(3,2,1)-标号数,并给出了一般图的L(3,2,1)-标号数的一个上界.     

图的{P4}——分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上．记Pl长度为l-1的路，如果G能够分解成若干个Pl，则称G存在{Pl}——分解，关于图的给定长路分解问题主要结果有：（i）连通图G存在{P3}-分解当且仅当G有偶数条边（见[1]）；（ii）连通图G存在{P3，P4}-分解当且仅当G不是C3和奇树，这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树（见[3]）．本文讨论了3正则图的{P4}--分解情况，并构造证明了边数为3k（k∈Z且k≥2）的完全图Kn和完全二部图Kr,s存在{P4}-分解.     

浅析图论教学

图论是《离散数学》课程的重要组成部分,也是数学专业高年级的选修课程.本文介绍了从事图论教学和研究的一些心得,探讨了如何在该课程的教学过程中激发学生的学习兴趣和培养学生的发现问题及解决问题能力,从而为学生今后作毕业论文或者进一步从事科学研究打下基础.     

树的笛卡儿积的测地数

图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笛卡儿积的测地数.     

有向图的L(j,k)数的上界

给定正整数j≥k,有向图D的一个L(j,k)-标号是指从V(D)到非负整数集的一个函数f,使得当x在D中邻接到y时|f(x)-f(y)|≥j,当x在D中到y距离为二时|f(x)-f(y)|≥k.f的像元素称为标号.L(j,k)一标号问题就是确定(?)j,k-数(?)j,k(D),这个参数等于(?) max{f(x)|x∈V(D)},这里f取遍D的所有L(j,k)-标号.本文根据有向图的有向着色数及最长有向路的长度来研究(?)j,k-数,证明了:(1)对任何有向着色数为(?)(D)的有向图D,(?)j,k(D)≤((?)(D)-1)j;(2)对任何最长有向路的长度为l的有向图D,如果不含有向圈或者D中最长有向圈长度为l 1,则(?)j,k(D)≤lj.并且这两个界都是可达的.最后我们对l=3的有向图给出了3j-L(j,k)-labelling的一个有效算法.     

弦图的L(3,2,1)}-标号

图 G 的一个 L(3,2,1)- 标号是指从 V(G) 到非负整数集的一个映射 f, 满足: 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 3; 当 d_G(u,v)=2 时, |f(u)-f(v)|\geq 2; 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 1. L(3,2,1)-标号问题就是确定出最小的整数 \lambda_3(G) 使得 G存在最大标号不超过该数的 L(3,2,1)- 标号. 本文研究了弦图的 L(3,2,1)- 标号问题,获得了弦图及其一些子类, 如扇, r- 路,r- 树等的 \lambda_3 数的界.     

圈的中间图pebbling数和Graham猜想

图G的一个pebbling移动是从一个顶点移走2个pebble, 而把其中的1个pebble移到与其相邻的一个顶点上. 图G 的pebbling数f(G)是最小的正整数n, 使得不论n个pebble 如何放置在G的顶点上, 总可以通过一系列的pebbling移动, 把1个pebble移到图G的任意一个顶点上. 图G 的中间图M(G) 就是在G 的每一条边上插入一个新点, 再把G 上相邻边上的新点用一条边连接起来的图. 对于任意两个连通图G和H, Graham猜测f(G\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想.     

关于k树的谱半径

洪渊给出了谱半径最大的k树.该文进一步定义了关于k树的一个参数l(G),借之给出了谱半径达到第二大和第三大的k树.