直径为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-完全的.     

3-正则无爪图的导出匹配覆盖(英文)

The induced matching cover number of a graph G without isolated vertices, denoted by imc（G）,is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V（M1）∪V（M2）∪···∪V（Mk）covers V（G）.This paper shows that,if G is a 3-regular claw-free graph,then imc（G）∈{2,3}.     

树的导出匹配覆盖

The induced matching cover number of a graph G without isolated vertices,denoted by imc(G),is the minimum integer k such that G has k induced matchings M1,M2,…,Mk such that,M1∪M2 ∪…∪Mk covers V(G).This paper shows if G is a nontrivial tree,then imc(G) ∈ {△*0(G),△*0(G) + 1,△*0(G)+2},where △*0(G) = max{d0(u) + d0(v) :u,v ∈ V(G),uv ∈ E(G)}.     

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

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

The Maximum Number of Dominating Induced Matchings

A matching M of a graph G is a dominating induced matching (DIM) of G if every edge of G is either in M or adjacent with exactly one edge in M. We prove sharp upper bounds on the number of DIMs of a graph G and characterize all extremal graphs. Our results imply that if G is a graph of order n, then ; provided G is triangle‐free; and provided and G is connected.     

图的导出森林2-划分

对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．     

Perfect Matchings Avoiding Several Independent Edges in a Star‐Free Graph

In Aldred and Plummer (Discrete Math 197/198 (1999) 29–40) proved that every m‐connected ‐free graph of even order has a perfect matching M with and , where F₁ and F₂ are prescribed disjoint sets of independent edges with and . It is known that if l satisfies , then the star‐free condition in the above result is best possible. In this paper, for , we prove a refinement of the result in which the condition is replaced by the weaker condition that G is ‐free (note that the new condition does not depend on l). We also show that if m is even and either or , then for m‐connected graphs G with sufficiently large order, one can replace the condition by the still weaker condition that G is ‐free. The star‐free conditions in our results are best possible.     

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.     

带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.     

Powers of the Vertex Cover Ideal of a Chordal Graph

In this article, Cohen–Macaulay chordal graphs and generalized star graphs are studied to show that all powers of the vertex cover ideal of such graphs have linear quotients. Moreover, it is shown that the Alexander dual of the clique complex of any chordal graph is vertex decomposable.