正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

强正则图与Seidel变换

本文通过对图的Seidel变换进一步研究，得到了一些新的强正则图。     

一类变换图的连通性

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

最大匹配的路变换图

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

控制过程方差的CUSUMQ图及其性质

崔恒建．控制过程方差的ＣＵＳＵＭＱ图及其性质．数理统计与管理，１９９８，１７（４），３３～３８．Ｑｕｓｅｎｂｅｒｒｙ（１９９５）基于样本方差的标准化变换Φ－１［Ｈｎ－１（（ｎ－１）Ｓ２／σ２０）］提出了控制过程方差的累积和（ＣＵＳＵＭ）Ｑ控制图。本文我们描述了在控制过程方差变化中这种ＣＵＳＵＭＱ控制图的性质，并将控制图的设计方法用到单边及双边的ＣＵＳＵＭＱ图，说明它几乎是最优的。而且我们发现在控制过程方差的微小变化时，设计的ＣＵＳＵＭＱ图的性能要优于基于ｌｏｇ（Ｓ２）的ＣＵＳＵＭ和ＥＷＭＡ图     

变换图的正则性和谱半径

在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计．     

三圈图的极小广义和连通指数

图的广义和连通指数作为新提出的一类分子拓扑指数,在QSPR/QSAR中有很大的应用价值.树图、单圈图和双圈图的极值问题已取得很多结果,而三圈图相关问题的研究较为复杂.限制-1≤α0,对三圈图的广义和连通指数进行了研究.通过对三圈图的分析,构造了一种图的变换,指出在三圈图中广义和连通指数的极小值必由其中的七种类型图取得.然后通过悬挂边的变换,最终得到三圈图广义和连通指数的极小值并刻画了唯一的极图.     

几乎完全分部图是本质链环图的一个充分条件(英文)

设G是去掉两条边的完全p-部图(p3),且是本质纽结图,经过有限次△-Y变换或点扩张得到图J.本文证明了,若从J中去掉任一顶点及与其相关联的所有边,则所得的图为一个本质链环图.这一结果给出了更多的本质纽结图满足Adams的纽结书中所提出的经典猜想"去掉本质纽结图的任一顶点得到的一定是本质链环图".     

几乎完全分部图是本质链环图的一个充分条件(英文)北大核心CSCD

设G是去掉两条边的完全p-部图(p<3),且是本质纽结图,经过有限次△-Y变换或点扩张得到图J.本文证明了,若从J中去掉任一顶点及与其相关联的所有边,则所得的图为一个本质链环图.这一结果给出了更多的本质纽结图满足Adams的纽结书中所提出的经典猜想"去掉本质纽结图的任一顶点得到的一定是本质链环图".     

渺位六角系统完美匹配Z——变换图

六角系统是2-连通的平面图，其每个内部面都是单位正六边形．六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构．一个六角系统H完美匹配Z—变换图Z（H）是一个图，它的顶点集是H的完匹配集，两个匹配相邻当且仅当它们的对称差是一个单位正六边形．本文用乘积图刻划了沙位六角系统Z—变换图的结构．     

On a connection between facility location and perfect graphs

We characterize the graphs for which a linear relaxation of a facility location problem defines a polytope with all integral extreme points. We use a transformation to a stable set problem in perfect graphs. Based on this transformation, these graphs can be recognized in polynomial time.     

新的Q整图类K_n~(-tk2)

在他人研究整图,Laplace整图和Seidel-整图的基础上,刻画了Q整图新类.对图类K-tk2n的无符号拉普拉斯特征多项式进行研究分析,应用矩阵的初等变换,给出了图类K-tk2n是Q整图的充分必要条件,得到了新的Q整图类K-tk2n及其Q谱.     

Graphs with the maximum or minimum number of 1-factors

Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.     

Semigroups of mappings on graphs

At present, there are quite a few investigations in the theory of semigroups devoted to semigroups of mappings on graphs. Up to now, endomorphism semigroups of graphs, extensive transformation semigroups of graphs, coloring semigroups of graphs and other semigroups of special mappings on graphs have been studied. The results obtained show the way graphs are determined by the above-mentioned semigroups. They also show the structure of semigroups of mappings and interrelations between properties of graphs and corresponding properties of semigroups associated with the graphs. This paper gives a survey of the main results in this field.     

Wagner's theorem for Torus graphs

Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation.     

An extrinsic characterization of addressable data graphs

Previous characterizations of the class of addressable data graphs have been intrinsic in nature. In this note, the auxiliary concept of a monoid system is used to derive an extrinsic characterization of the class. Specifically, a partial transformation of the class of data graphs is found which fixes (up to isomorphism) precisely the addressable data graphs.     

完全六部图是S-整图的一个充要条件

在他人研究完全多部图的邻接谱的基础上,对整完全多部图的Seidel多项式进行研究分析,以期得到完全六部图G是S-整图的充要条件．从讨论完全六部图的Seidel多项式入手,应用矩阵行初等变换的方法给出完全六部图G是S-整图的充要条件．