变换图G以及变换图G的一些性质

摘要

设G=(V(G)，E(G))是简单图，Wu Baoyindureng等将全图的概念推广，得到变换图的概念.变换图Gxyz，x，y，z∈{+，-}，以V(G)∪ E(G)为其顶点集，对任意的α,β∈V(G)∪E(G)，α和β在图Gxyz中邻接的条件如下：(ⅰ)α，β∈V(G)，x=+时当且仅当α和β在图G中相邻；x=-时当且仅当α和β在图G中不相邻.(ⅱ)α，β∈E(G)，y=+时当且仅当α和β在图G中相邻；y=-时当且仅当α和β在图G中不相邻.(ⅲ)α∈V(G)，β∈E(G)，z=+时当且仅当α和β在图G中关联；z=-时当且仅当α和β在图G中不关联.G+++即为G的全图T(G). 近年来陆续有学者对包括全图在内的变换图进行了研究，也取得了不少成果，如变换图的连通性，边连通度，直径，正则性等等.但是到目前为止，针对变换图的研究成果还较少，对变换图的性质还有很大的研究空间.本文主要针对变换图G--+的一些性质进行了研究，具体结论如下： 1.G--+的可平面性： 除了K1，2K1，K2，3K1，K2+K1，P3，K3，4K1，K2+2K1，P3+K1，K1.3，K3+K1这12个图G外，G--+都不是可平面图. 2.G--+的同构： (1)G--+≌Pn--+当且仅当G≌Pn. (2)G--+≌Hn--+当且仅当G≌Hn，其中Hn(n≥6)如图2.2.1(a)所示. (3)若G连通，则G--+≌Cn--+当且仅当G≌Cn. 此外，中图M(G)也是被广泛研究的一种变换图.受中图补图M(G)定义的启发，我们定义了下类变换图.变换图G﹡xy，x,y∈{+，-}，以V(G)u∪E(G)为其顶点集，对任意的α，β∈y(G)u∪E(G)，α和β在图G﹡xy中邻接的条件如下：(ⅰ)α，β∈V(G).(ⅱ)α，β∈E(G)，x=+时当且仅当α和β在图G中相邻；x=-时当且仅当α和β在图G中不相邻.(ⅲ)α∈V(G)，β∈E(G)，y=+时当且仅当α和β在图G中关联；y=-时当且仅当α和β在图G中不关联.类似的，我们也对这类变换图的一些性质进行了研究，结论有： 1.G﹡xy的连通性： (1)对任意图G，G﹡+--连通当且仅当G≠K2(2)对任意图G,G﹡-+都是连通的. (3)对任意图G，G﹡++都是连通的. 2.G*xy的直径： (1)若G≠ K2，则diam(G﹡--)≤3，等号成立当且仅当G≌ P3或K3. (2)若G≠ K2，则diam(G﹡+-)≤3，等号成立当且仅当G≌ 2K2. (3)设G是图，则diam(G﹡-+)≤2. (4)设G是图，则diam(G﹡++)≤3，等号成立当且仅当G包含2K2作为它的点导出子图. 3.G﹡xy的正则性： (1)G﹡--是正则图当且仅当G是空图. (2)G﹡+-是正则图当且仅当G为C3，K4或空图. (3)G﹡-+是正则图当且仅当G为10阶3-正则图，8阶4-正则图，K7，K2或空图. (4)G﹡++是正则图当且仅当G是完全图或空图. 4.G﹡xy的独立数： (1)对任意图G，△(G)≤α(G﹡-+)≤△(G)+2.α(G﹡-+)=△(G)+2当且仅当K3是G的真子图且△(G)=2.α(G﹡-+)=△(G)当且仅当△(G)=n-1且G不同构于K3、K4、K4-e及G1，其中G1如图3.4.1所示. (2)对任意图G，α(G﹡+-)=α’(G)或α'(G)+1.α(G﹡+-)=α’(G)+1当且仅当G同构于K1，r+mK1、K3+mK1、K3+mK1(m≥0)或G为空图. (3)对任意图G，α(G﹡++)=α’(G)或α’(G)+1.α(G﹡++)=α’(G)当且仅当G有完美匹配.

目录

声明

摘要

第1章前言

1.1定义和记号

1.2有关变换图的一些结论及本文的主要工作

第2章满足xyz=--+的变换图Gxyz

2.1 G--+的可平面性

2.2 G--+的同构

第3章变换图G*xy的基本性质

3.1 G*xy的连通性

3.2G*xy的直径

3.3 G*xy的正则性

3.4G*xy的独立数

第4章可以进一步研究的问题

参考文献

申请硕士学位期间完成的工作

致谢