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

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

导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性

图Ｇ的一个匹配Ｍ是导出的,若Ｍ是图Ｇ的一个导出子图。图Ｇ是导邮匹配可扩的（简记ＩＭ－可扩的）,若图Ｇ的任一导出匹配均含于图Ｇ的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图Ｇ以及一个正整数ｒ,确定是否存在图Ｇ的一个导出匹配Ｍ使得Ｍ≥ｒ”是ＮＰ－完全的。⑵对直径为２的图以及直径为３的偶图,问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ完全的;而对完全多部图而言,问题“     

无爪图的导出匹配可扩性

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

匹配可扩图的结构

设G是一个有限的简单连通图。D（G）表示V（G）的一个子集,它的每一个点至少有一个最大匹配不覆盖它。A（G）表示V（G）-D（G）的一个子集,它的每一个点至少和D（G）的一个点相邻。最后设C（G）=V（G）-A（G）-D（G）。在这篇章中,下面的被获得。⑴设u∈V（G）。若n≥1和G是n-可扩的,则（a)C(G-u)=φ和A（G-u)∪{u}是一个独立集,（b)G的每个完美匹配包含D（G-u)的每个分支的一个几乎守美匹配,并且它匹配A（G-u)∪{u}的所有点与D（G-4）的不同分支的点。⑵若G是2-可扩的,则对于u∈V（G）,A（G-u）∪{u}是G的一个最大障碍且G的最大障碍的个数是2或是│V(G)│.⑶设X=Cay(Q,S),则对于u∈Q,(a)A(X-u)=φ=C（G-u)和X-u是一个因子临界图,或（b)C(X-u)=φ和X的两部是A（X-u)∪{u}和D（X-u)且│A(X-u)∪{u}│=│D(X-u）│。⑷设X=Cay(Q,S),则对于u∈Q,A（X-u)∪{u}是X的一个最大障碍且X的最大障碍的个数是2或是│Q│。     

循环图C_(2n)(1,(2n+1)/3)的匹配可扩性

称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.根据循环图的性质研究了图C_(2n)(1,(2n+1)/3)的匹配可扩性,证明了对于任意的n(n≥4),C_(2n)(1,(2n+1)/3)是3-偶匹配可扩的.     

I-图的可扩性

如果连通图I中任意n条点不交的边都包含在一个完美匹配中,就称I是n-可扩的.证明了真I图I(n,j,k)是1-可扩的;当n≠3j或者3k时,真I-图是2-可扩的.     

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G, 如果对于V(G)的任意k元子集S, 子图G-S都包含分数完美匹配, 那么称G为分数k-因子临界图. 如果图G的每个k-匹配M都包含在一个分数完美匹配中, 那么称图G为分数k-可扩图. 给出一个图是分数k-因子临界图和分数k-可扩图的充分条件, 并给出一个图是分数k-因子临界图的充分必要条件.     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

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

奇图的匹配可扩性

设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.     

3阶幂图的广义导出匹配可扩性

A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maximum matching of G. A graph G is claw-free, if G dose not contain any induced subgraph isomorphic to K1,3. The k-th power of G, denoted by Gu, is the graph with vertex set V（G） in which two vertices are adjacent if and only if the distance between them is at most k in G. In this paper we show that, if the maximum matchings of G and G3 have the same cardinality, then G3 is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if G is a connected claw-flee graph, then G3 is generalized induced matching extendable.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

Induced Matching Extendable Graph Powers

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. We obtain the following two results which give positive answers to two conjectures of Yuan. Result 1. If a connected graph G with |V(G)| even is locally connected, then G² is strongly IM-extendable. Result 2. If G is a 2-connected graph with |V(G)| even, then G³ is strongly IM-extendable. Research Supported by NSFC Fund 10371102.     

Extremal Graphs With a Given Number of Perfect Matchings

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.     

一类新图的匹配唯一性

利用图的匹配多项式及其最大实数根的性质证明了树T(1,1,n,2,1)及补图匹配唯一的充要条件是n≠1,2,5,8.     

图匹配多项式的因式分解及其应用

通过讨论几类图簇匹配多项式的因式分解,给出了两类图簇匹配等价图的结构性质,从而得到几类新的非匹配唯一图.