小直径图的导出匹配覆盖

设G是一个图,而M1,M2,…,Mk是G的k个导出匹配.称{M1,M2,…,Mk}是图G的一个k-导出匹配覆盖,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解.     

关于元爪图的一个性质(英文)

In this paper we consider a property of claw-free graphs.We show that if d（u）＋ d（v）≥ν（G）＋2k＋3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν（G）=｜V（G）｜.And the bound is tight.     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

无爪图的导出匹配可扩性

若图G的一个匹配M也是G的点导出子图,则称M是图G的一个导出匹配．我们称图G是导出匹配可扩的,若它的任何一个导出匹配可以扩充成一个完美匹配,本文我们讨论无爪图的导出匹配可扩性,得出如下结论,并同时指出这些结果是最好可能的．设图G是有2n个顶点的无爪图,1．若图G是最小度大于或等于2 1,则图G是导出匹配可扩的．2．若图G是局部2连通的,则留G是导出匹配可扩的．3．若图G是k正则的且k≥n,则图G是导出匹配可扩的．     

几乎无爪图的叶子数较少的生成树

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree.In this paper, we prove that if G is a k-connected(k ≥ 2) almost claw-free graph of order n and σ_(k+3)(G) ≥ n + k + 2, then G contains a spanning 3-ended tree, where σk(G) =min{∑_(v∈S)deg(v) : S is an independent set of G with |S| = k}.     

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

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

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.     

关于3正则图的三匹配交猜想(Ⅱ)

Fan和Raspaud 1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配．本文证明了如下结果：若G是一个圈4-边连通的无桥3正则图，且存在G的一个完美匹配M1使得G—M1恰为4个奇圈的不交并，则存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=Φ。     

3-正则Halin-图全色数的注(英文)

本文讨论了△（G）＝3的Halin-图的金色数Xr（G）＝4的充分条件，并提出了3－正则Halin-图Xr（G）＝5的充分必要条件的猜想，其中△（G），Xr（G）分别表示G的最大度和全色数．     

3－连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ—４的３－连通ｋ－正则无爪图是Ｈａｍｉｌｔｏｎ的．     

导出匹配,极大导出匹配可扩图和导出匹配数

目前我们已知的极大导出匹配可扩图只有Kn,n和K2n.为了研究它们是否是仅有的极大导出匹配可扩图,我们考虑了匹配数,导出匹配数,极大导出匹配可扩图以及一个相关的猜想,并得出了若干相关的结果.     

On the Clique-Transversal Number in （Claw,K4）-Free 4-Regular Graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC(G),is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC(G) and characterize the extremal graphs achieving the lower bound for a connected(claw,K4)-free 4-regular graph G.Furthermore,we show that for any 2-connected(claw,K4)-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性

给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的.     

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

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

Maximum independent sets in 3- and 4-regular Hamiltonian graphs

Smooth 4-regular Hamiltonian graphs are generalizations of cycle-plus-triangles graphs. While the latter have been shown to be 3-choosable, 3-colorability of the former is NP-complete. In this paper we first show that the independent set problem for 3-regular Hamiltonian planar graphs is NP-complete, and using this result we show that this problem is also NP-complete for smooth 4-regular Hamiltonian graphs. We also show that this problem remains NP-complete if we restrict the problem to the existence of large independent sets (i.e., independent sets whose size is at least one third of the order of the graphs).     

A Distributive Lattice on the Set of Perfect Matchings of a Plane Bipartite Graph

Let G be a plane bipartite graph and M(G) the set of perfect matchings of G. The Z-transformation graph of G is defined as a graph on M(G): M,MM(G) are joined by an edge if and only if they differ only in one cycle that is the boundary of an inner face of G. A property that a certain orientation of the Z-transformation graph of G is acyclic implies a partially ordered relation on M(G). An equivalent definition of the poset M(G) is discussed in detail. If G is elementary, the following main results are obtained in this article: the poset M(G) is a finite distributive lattice, and its Hasse diagram is isomorphic to the Z-transformation digraph of G. Further, a distributive lattice structure is established on the set of perfect matchings of any plane bipartite graph.