李亚平，吴宝音都仍

(新疆大学 数学与系统科学学院, 新疆 乌鲁木齐, 830046)

0 引言

设G=(V(G),E(G)) 是一个简单无向图. 对没有说明的术语和概念可参考[1, 2]. 图G的一个点v, 在G中的度记为dG(v),v的邻点记为NG(v) 是{u∈V(G)|uv∈E(G)}. 两个点u和v之间的距离dG(u,v)是它们之间最短路的长度.

我们用符号∆(G),δ(G),κ(G),λ(G),α(G),α′(G) 和ω(G) 分别表示G的最大度, 最小度, 连通性, 边连通性,独立数, 匹配数和团数. 图G的连通性(边连通性)记为κ(G)(λ(G)), 被定义为使G是k−连通的(k−边连通的)最大整数k. ∆′(G)=max{dG(u)+dG(v)|uv∈E(G)}.

图G的补图, 记为, 它的点集与G的相同, 且其两个点相邻当且仅当它们在G中不相邻. 图G的线图, 记为L(G), 它的顶点为E(G), 两个点相邻当且仅当在G中它们作为边是相邻的. 图G的全图T(G) 的点集是V(G)∪E(G), 且两个点相邻当且仅当它们在G中相邻或关联.

设G=(V(G),E(G)) 是一个图, 且α,β是V(G)∪E(G)的两个元素. 如果α和β在G中是相邻的或关联的,我们就说它们的关系是+. 设xyz是集合+,−的3-置换. 如果α和β都在V(G)中(分别地,α和β都在E(G) 中或α和β中的一个在V(G)另一个在E(G)中), 我们就说α和β对应于xyz的第一项x(分别地, 第二项y或第三项z).

图G的变换图Gxyz定义在点集V(G)∪E(G)上,Gxyz的两个点α和β是由一条边相邻的当且仅当它们在G中的关系和xyz的对应项相一致.因为有+,−的8个不同的3-置换,我们得到了8个图G的变换图. 有趣的是G+++恰好是G的全图T(G), 且G−−−是T(G)的补图. 又对给定的图G,G++−和G−−+,G+−+和G−+−,G−++和G+−−是其它的3对互补图.

变换图Gxyz作为全图的变换是由吴和孟[1]在2001年首次引进的，所有这些变换图都具有很多好的性质.

1 基本性质

若uv是G中的一条边, 则我们用euv记为Gxyz中的点. 吴和孟[1]给出了Gxyz是连通的充分必要条件, 对……