双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

3-正则图的不共边的完美匹配（英文）

研究3-正则图的一个有意义的问题是它是否存在k个没有共边的完美匹配.关于这个问题有一个著名的Fan-Raspaud猜想：每一个无割边的3-正则图都有3个没有共边的完美匹配.但这个猜想至今仍未解决.设dim（P（G））表示图G的完美匹配多面体的维数.本文证明了对于无割边的3-正则图G,如果dim（P（G））≤14,那么k≤4：如果dim（P（G））≤20,那么k≤5.     

非连通图G1∪G2及G1∪G2∪K2的优美性

将k-优美图的概念进行了推广，引入了k-l优美图及标号间距的概念，并以此为基础，分别推出了一般情形下判定非连通图G1∪G2及G1∪G2∪K2是优美图的两个充分条件；同时得出了图（C3VK^-n）∪st（m）∪K2是优美图，其中k、l为自然数，l〈k，C3是长为3的圈，Kn为n个顶点的完全图，K^-n是Kn的补图，St（m）表示m＋1个顶点的星形树，C3VK^-n是C3与K^-n的联图．     

强完美图定理及相关的问题

介绍强完美图定理(The Strong Perfect Graph Theorem,SPGT)的历史和获证经过,同时简述SPGT被克服后生发的一些新问题,以期对图理论的一般研究起到鼓励和促进作用.因具体的证明浩大聱曲,在技术的部分仅注重框架而不涉及细节.     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

关于P（n1,n2,...nm）和Dm,4的优美性

一个简单图G=(V,E)是k-优美的(k≥1的整数),如果存在一个1-1映射 f:V(G)→(0,1,…,|E| k-1)使得对所有的边e=wv∈E(G),由f~*(u,v)=|f(u)-f(v)|导出的映射 E(G)→{k,k 1,…,|E| k-1}是一个1-1对应。这个关于k-优美的概念是由Slater和Thuillier相互独立地提出来的。当k=1,就是我们通常研究的优美图。显然,k-优美图一定是1-优美图。反之不真。例如,三回路c_3是1-优美图,但对k>1,非k-优美。     

3-边可染的3-正则图（英文）

若一个连通图的每条边都包含在某一完美匹配中,则称之为匹配覆盖图.设G是一个3-连通图,若去掉G的任意两个顶点后得到的子图仍有完美匹配,则称G是一个brick.而brick的重要性在于它是匹配覆盖图的组成结构因子.3-边可染3-正则5的刻画问题是一个NP-完全问题.本文将此问题规约到3-正则匹配覆盖图上,进而规约到其组成结构因子brick上.我们证明了:一个3-正则图是3-边可染的当且仅当它的所有brick是3-边可染的.     

关于二次型图的完美性

本文应用强完美图定理,解决了二次型图的完美图判别问题.     

关于图B（m,n,p）的优美性

在［１］［２］中已证明“除去三种特殊情形，连结两个顶点的三条独立路所成简单图Ｂ（ｍ，ｎ，ｐ）是优美图”，并猜想：对除去的三种情形，Ｂ（ｍ，ｎ，ｐ）也是优美的。本文证实了上术猜想。这样一来，也就证明了［３］中的猜想：有－ｈ－链弦的圈是优美的（ｈ≥２）。     

具有唯一完美匹配的D-图

为了研究具有完美匹配图的Tuttc集和极端集,文献[1,2]提出了一种新的图运算,并且得到了许多有趣的性质。本文中,我们刻画了level（G）=0的具有唯一完美匹配的饱和图G,并且确定了具有唯一完美匹配图的D-图的边数的紧上界。     

On Perfect 2‐Colorings of Johnson Graphs J(v, 3)

We study the perfect 2‐colorings (also known as the equitable partitions into two parts or the completely regular codes with covering radius 1) of the Johnson graphs . In particular, we classify all the realizable quotient matrices of perfect 2‐colorings for odd v. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 232–252, 2013     

Partitioning Perfect Graphs into Stars

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs.     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

Perfect State Transfer on Weighted Abelian Cayley Graphs*

Recently, there are extensive studies on perfect state transfer (PST for short) on graphs due to their significant applications in quantum information processing and quantum computations. However, there is not any general characterization of graphs that have PST in literature. In this paper, the authors present a depiction on weighted abelian Cayley graphs having PST. They give a unified approach to describe the periodicity and the existence of PST on some specific graphs.     

P5,4m的优美性

设u,v是两个固定顶点,用b条内部互不相交且长度均为a的道路连接u、v所得到的图用Pa,b表示。Kathiresan证实P2r,2m-1(r,m均为任意正整数)是优美的,且猜想:除了(a,b)=(2r 1,4s 2)外,所有的Pa,b都是优美的。杨元生已证实P2r 1,2m-1是优美的,本文证明m=2n(2l-1),(0≤n≤4,l∈N)时,P5,4m是优美图。     

On the Determination Problem for P 4-Transformation of Graphs

We prove that the P ₄-transformation is one-to-one on the set of graphs with minimum degree at least 3, and if graphs G and G ^' have minimum degree at least 3 then any isomorphism from the P ₄-graph P ₄(G) to the P ₄-graph P ₄(G ^') is induced by a vertex-isomorphism from G to G ^' unless G and G ^' both belong to a special family of graphs. Supported by NSFC, PCSIRT and the “973” program.     

3-连通(X,Y)-free图的Hamiltonian-连通性

一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的.     

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.