二部图上完美匹配的正交匹配分解

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。     

具有八个节点的自补图

In this note we deduce that there are exactly 10 self complement graphs on 8 vertices (G=G), which is characterized in the sort of degree sequences . It is a correction to the assertation made by Harary ( [ 1 ]) .     

Path Decomposition of Graphs with Given Path Length

A path decomposition of a graph G is a list of paths such that each edge appears in exactly onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_l is a path of length l-1.Similarly,G is said to admit a {P_l,P_k}=decomposition if G can be decomposed intosome copies of P_l or P_k.An k-cycle,denoted by C_k,is a cycle with k vertices.An odd tree is a tree of which allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.     

关于有向图的强符号可解性

Hansen已提出一个判别强符号可解有向图的一般算法,其时间复杂性为O(mn).仔细分析算法,尚存在很多重复过程而耗费时间。从图论的观点看,最有效的算法应当是O(m)。本文进一步研究强符号可解有向图的一些基本性质,在此基础上发现这类图存在一种嵌套结构。结合有向图的DFS纵深搜索法,我们找到一个最有效的递推算法,其时间复杂性恰为O(m)。从而,使符号有向图的判别问题满意地获得解决。     

GENERALIZED WEIGHT

In this paper the generalized weight is introduced, and its behaviour is discussed.     

答YapH.P.和TeoS.K.问题

本文证得：如果Ｆ是Ｃｎ中的一条种路，则Ｇ中同时通过ｋ余弦ｅ１，ｅ２，．．．，ｅｋ而不通过Ｆ中的任一条边的圈最多只有一个且Ｇ中同时通过ｋ条弦ｅ１，ｅ２，．．．，ｅｋ的圈最多只有２个，进而由之给出了Ｍ（ｋ）的上界和ｍ（ｋ）的下界及ｍ（ｋ）＝（ｋ＋１）（ｋ＋２）／２成立的一个条件，否定地回答了ＹａｐＨ．Ｐ．和ＴｅｏＳ．Ｋ．１９８４年提出的一个问题。     

关于图的循环带宽的一些结果

本文给出关于图的循环带宽的一些结果．     

可平面图完备色数唯一性问题

可平面图完备色数唯一性问题赵克文（华南师范大学数学系，广州５１０６３１）我们已经知道，图的点色数、边色数，点边金色数Ｘ＿Ｔ都是唯一的。那么，可平面图的边面完备色数Ｘ唯一吗￣［２］？本文对此有结论：并非每一可平面图的完备色数都唯一，由此就产生问题：Ｘ（...     

图的树宽的结构性结果

图G的树宽是使得G成为一个k-树的子图的最小整数k．树宽的算法性结果在图子式理论及有关领域中已有深入的研究．本文着重讨论其结构性结果，包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质．