论文部分内容阅读
设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有完美匹配.