一类笛卡儿乘积图的PM-紧邻性质

图G的完美匹配图,记为PM(G),是以G的每个完美匹配作为顶点并且两个顶点相邻当且仅当这两点对应于G中两个完美匹配的对称差恰好是一个圈而得到的图.若PM(G)是完全图,则称G是完美匹配紧邻的,简称G是PM-紧邻的.研究了一类笛卡儿乘积图的PM-紧邻性质,完全刻画在这类笛卡儿乘积图中所有的PM-紧邻图.

树和路乘积图的L(s,t)边跨度(英文)

图的L(s,t)-标号的概念来自频道分配问题.设s和t是2个非负整数.图G的一个L(s,t)-标号是一个从G的顶点集到整数集的映射,满足:①任意2个相邻顶点对应的整数相差至少为s;②任意2个距离为2的顶点对应的整数相差至少为t.给定图G的一个L(s,t)-标号f,f的L(s,t)边跨度定义为max{f(u)-f(v) :(u,v)∈E(G)},记为βst(G,f).图G的L(s,t)边跨度定义为min{βst(G,f):f取遍图G的所有L(s,t)-标号},记为βst(G).设T是一棵最大度为Δ(≥2)的树.证明了:若2s≥t≥0,则βst(T)=(Δ/2 -1)t+s;若0≤2s<t且Δ为偶数,则βst(T)=(Δ-1)t/2;若0≤2s<t且Δ为奇数,则βst(T)=(Δ-1)t/2 +s.同时完全确定了2条路的笛卡儿乘积图和正四边形格图的L(s,t)边跨度.

一类笛卡儿积图中可去边的研究

对于任一有完美匹配的连通图G(δ (G)≥2)和包含l个顶点的路P_(l)(l≥4),证明它们的笛卡儿乘积图G×P_(l)为匹配覆盖图,且每条边都是可去边.

图的距离标号与频率分配问题

图的L(2,1)-标号问题由频率分配问题归结而来.图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v):v∈ V(G)}=k的L(2,1)-标号中的最小数k.本文将L(2,1)-标号问题推广到更一般的情形即L(4,3,2,1)标号问题,并得出了笛卡儿乘积图的λ4(G)的上界.