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

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

Number of Induced Matchings of Graphs

A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.     

几类图的匹配唯一性

若图G的匹配多项式为M(G;W),对任何图H,M(G;W)=M(H;W)推出G与H同构,则称G是匹配唯一的.本文讨论了下面的几种图类:(i)B_(m,n,r);(ii)D_(m,n,r);(iii)T_(m,n)的匹配唯一性问题,从而得到一些较为满意的结果.     

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

Continuous Forcing Spectra of Even Polygonal Chains

Let G be a graph that admits a perfect matching M.A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G.The cardinality of a forcing set of M with the smallest size is called the forcing number of M,denoted by f(G,M).The forcing spectrum of G is defined as:Spec(G)={f(G,M)|M is a perfect matching of G}.In this paper,by applying the Ztransformation graph(resonance graph)we show that for any polyomino with perfect matchings and any even polygonal chain,their forcing spectra are integral intervals.Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks.Forcing spectra of two extremal chains are determined.     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

Some graphs which have ascending subgraph decomposition

1.IntroductionIn[1],Alavietal.gavethefollowingdecompositionconjecture.Conjecture.LetGbeagraphwith("1')edges.ThentheedgesetofGcanbedecomposedintonsetsgeneratinggraphsGI,G2,'IG.suchthatIE(Gi)I=i(fori=1,2,',n)andGiisisomorphictoasubgraphofGi 1fori=1,2,'.)n--1.AgraphGthatcanbedecomposedasdescribedinConjecturewillbesaidtohaveanAscendingSubgraphDecomposition(AlsoabbreviatedasASD).ThesubgraphsGIIG2,',G.aresaidtobemembersofsuchadecomposition.Furthermore,ifeachGiisastar(matching,pat…     

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.     

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical.     

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

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

大围长图的广义无圈染色

图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.     

树的导出匹配覆盖

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)}.     

导出匹配可扩图的局部运算

称图G为导出匹配图可扩的（简称为IM－可扩的），如果图G的一每个导出匹配都包含在G的一个完美匹配中，本给出了导出匹配可扩图的一些局部运算。     

TWO RESULTS ON GENERALIZED CHROMATIC NUMBERS

Abstract

The m'th chromatic number X_m(G) of a graph G is the least number of colours required to colour the vertices of G such that no m-clique of G is mono-coloured. For each k ≥ 2 and m ≥ 2 we determine for which r a graph G with m'th chromatic number k and clique number r exists. We also determine for which n a graph G exists with X_n (G + K) = X_m (G) = k.     

Die chromatischen Polynome unterringfreier Graphen

Let G be a finite undirected graph without loops and multiple edges. A graph is called “unterringfrei”, if there is no induced subgraph being a cycle of length?4. This note shows that the chromatic polynomial of such a graph does only have positive integers as its roots. Conversely all polynomials with only positive integral roots are the chromatic polynomials of such graphs under the slight restriction that M(G;α)=0 implies that M(G;β)=0 for α>β?0.     

立方图的对控制数

设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq V$, G[S]表示图G中由S所导出的子图. 如果S是G的一个控制集并且G[S]包含至少一个完备匹配, 则称S是G的一个对控制集. G中对控制集的最少的顶点数称为$G$的对控制数, 记为γ_p(G). 该文证明了对任意有n点的连通立方图G, γ_p(G)≤3n/ 5.     

ON MAXIMAL MATCHINGS OF CONNECTED GRAPHS

Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G. Let gk be a k-matching of G, if there exists a subset {e1, e2,…, ei} of E(G) \ gk, i (?)1, such that (1) for any j ∈ {1, 2,…,i}, gk + {ej} is a (k + l)-matching of G; (2) for any f ∈ E(G) \ (gk ∪ {e1,e2,…,ei}), gk + {f} is not a matching of G; then gk, is called an i wings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.     

DEGREE CONDITIONS OF INDUCED MATCHING EXTENDABLE GRAPHS

Abstract. A simple graph G is induced matching extendable,shortly IM-extendable,if every in-duced matching of G is included in a perfect matching of G. The degree conditions of IM-extend-able graphs are researched in this paper. The main results are as follows：