一类变换图的Wiener指数

研究了一类变换图G(R*,S*),其中R*=(r 1,r 2)且S*=(1,…,1),计算出变换图G(R*,S*)的Wiener指数公式,并给出变换图G(R*,S*)的Wiener指数的渐进性质.

变换图G^(--+)的超边连通性

如果λ(G)=δ(G),则称图G是极大边连通的;如果G的最小边割只能分离G的一个孤立点,则称图G是超边连通的.证明了对所有的有限图G,其变换图G--+都是极大边连通的,G--+是超边连通的当且仅当G不同构于K1,2也不同构于K2∪K1.

变换图G^(-+-)的极大边连通性

对任意图G=(V(G),E(G)),其变换图G^(-+-)的顶点集为V(G)∪E(G),顶点α和β在G^(-+-)中邻接当且仅当下列条件之一成立:当{α,β}■E(G)时,α和β在G中不邻接或不关联;当{α,β}■ E(G),α和β在G中邻接。证明了所有连通的变换图G^(-+-)都是极大边连通图。

满足xyz=--+的变换图G^(xyz)

图G的变换图G--+以V(G)∪E(G)为其顶点集,对任意的α,β∈V(G)∪E(G),α和β在图G--+中邻接的条件如下:(i)α,β∈V(G),且α和β在G中不相邻,(ii)α,β∈E(G),且α和β在G中不相邻,(iii)α∈V(G),β∈E(G),且它们在G中相关.本文主要证明除了12个图外,G--+都不是可平面图,以及对于图G,G--+≌Pn--+当且仅当G≌Pn.

变换图G^(++-)的超力连通性(英文)

对于图G,一般有λ(G)≤δ(G).如果λ(G)=δ(G),称图G是较大边连通的.如果G的每一个最小边割只能分离G的一个孤立点.称图G是超边连通的.本文证明了几乎所有的有限图G,其变换图G++-都是超边连通的.

变换图G^(+--)的极大边连通性(英文)

证明了对于任意的图G,其变换图G+--是极大边连通的当且仅当G至少有两条边且不同构于2K2．

一类变换图的距离性质

求得一类变换图G(R*,S*)(其中R*=(r1,r2),S*=(1,…,1))的直径为r,证明了对于G(R*,S*)中任意2个距离为k的点,恰存在k2条内部不交的最短路联结这2个点,并且最多存在(r1)(n-r1)条内部不交的路联结这2个点.

一类变换图的同构问题

利用度序列的概念,证明变换图G^(--+)与H_n^(--+)同构,当且仅当G与_n同构.以及在G连通的条件下,G^(--+)与C_n^(--+)同构,当且仅当G与_n同构.

Cayley图与变换图(Interchange Graph)

设s_x是n次对称群,M_x是由s_x的一些奇置换组成的共轭类,对任意n本文得到了Cayley图类Cay(M_x,S_x)的点连通度、直径、Hamiltonian 性及其它一些图论性质,同时本文还发现一类变换图G(R^x(1),S^x(1))与Cay(M,S_x)是同构的图类,(其中R^x(1),S^x(1)分别是n维全1行和、列和向量,M是s_x的对换全体),从而得到这类变换图与Cayley图Cay(M_x,S_x)相平行的一些性质。

一类变换图的递归构造方法

1980年,著名的图论专家R.A.Brualdi提出了关于变换图G(R,S)直径的Brualdi猜想[1],但至今仍悬而未决.J.Jin于2011年定义了一类变换图G(R*,S*)[2],其中,R*=(r1,r2)且S*=(1,…,1).本文根据G(R*,S*)中最大团的性质找到G(R*,S*)的递归构造方法.

最大匹配的路变换图

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.

变换图G^(*xy)的独立数

变换图的概念由全图推广而来。文章在中图的补图M(G)的定义启发下,定义了四类变换图,其中一个恰是(G),并探讨了这些变换图的独立数。研究了变换图G*-+的独立数与原图最大度的关系,以及G*++与G*+-的独立数与原图边独立数的关系。

每行和为1的(0,1)方阵变换图的若干性质

著名的图论专家R.A.Brualdi于1980年提出关于变换图直径的Brualdi猜想[1],然而至今却悬而未决.研究一类变换图G(R1*,S1*),R1*=(1,…,1)、S1*=(1,…,1)的若干性质,并给出其直径为n-1,最后提出若干有待解决的问题.

变换图的一个结构定理

为了刻划（０，１）－矩阵类Ａ（Ｒ，Ｓ）的变换图Ｇ（Ｒ，Ｓ）的结构，利用图的同构及同构映射，得到了Ｇ（Ｒ。

广义变换图G^(+∞)(R,S)的边连通度

记Ａ＋∞（Ｒ，Ｓ）为具有行和向量Ｒ及列和向量Ｓ的所有ｍ×ｎ阶非负整数矩阵的集合．广义变换图Ｇ＋∞（Ｒ，Ｓ）的顶点定义为Ａ＋∞（Ｒ，Ｓ）中的矩阵，两个顶点（矩阵）相邻当且仅当它们可通过一次变换相互得到．并证明Ｇ＋∞（Ｒ，Ｓ）的边连通度等于其顶点的最小度δ（Ｇ＋∞（Ｒ，Ｓ））．

一种基于双弧竞赛图的变换图

研究有相同得分向量的双弧竞赛图为顶点的变换图,并且得到这样的变换图是连通的;若G(S)的直径为d,则其连通度为d/2.

变换图G^(*xy)的基本性质

图G的变换图G*xy以V(G)∪E(G)为其顶点集,x,y∈{+,-}·对任意的α,β∈V(G)∪E(G),α和β在图G*xy中邻接的条件如下:(ⅰ)α,β∈V(G)·(ⅱ)α,β∈E(G),x=+时当且仅当α和β在图G中相邻;x=-时当且仅当α和β在图G中不相邻·(ⅲ)α∈V(G),β∈E(G),y=+时当且仅当α和β在图G中关联;y=-时当且仅当α和β在图G中不关联·主要介绍了四类变换图,其中一个恰是中图M(G)的补图,并探讨了这些变换图的一些基本性质·

四角系统的Z-变换图的Hamilton路

如果G表示一个四角系统,则G的Z-变换图Z(G)指如下定义的图:图Z(G)的所有顶点对应于四角系统G中的所有完美匹配,且Z(G)中的两个顶点有一条边相连当且仅当它们在G中对应的两个完美匹配的对称差恰好形成G的一个四角形.利用图同构的方法,证明了两类四角系统(L-四角系统和Z-四角系统)的Z-变换图必含有一条Hamilton路.

行数为2的变换图的若干性质

著名的图论专家Brualdi于1980年提出了关于变换图G(R,S)直径的Brualdi猜想,但至今仍悬而未决。本文定义行数为2的变换图G(R,S)为G(R^(*),S^(*)),其顶点数为[nr],边数为r(n-r)/2(nr),当r≤n/2时,G(R^(*),S^(*))是二部图,当且仅当n=2;G(R^(*),S^(*))是完全图,当且仅当r=1。根据变换图的性质,结合G(R^(*),S^(*))的最大团结构,对变换图G(1,4)、G(2,4)、G(2,5)和G(2,6)进行了作图。

一类变换图的连通性

本文定义了一类由给定的一个３－正则平面偶图的全体完美匹配所构成的变换图，并证明了该变换图是连通的．由此可得出结论：从任一给定的３－正则平面偶图的完美匹配出发，通过一种所谓的旋转运算，就可以生成全部其它的完美匹配．