极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

完全二部图的色性

设 G 是一个图,我们用 V(G)和 E(G)分别表示 G 的顶点集和边集,记 v=|V(G)|,ε=|E(G)|.P(G;λ)是图 G 的色多项式.称图 G 是色唯一的,如果任何图 H,由 P(H;λ)=P(G;λ),推知 H 与 G 同构.c_t(G)表示 G 中长为 k 的圈的个数.用G=(X,Y)表示二部图,K_(m,n)表示两部分的基数分别为 m 和 n 的完全二部图.本文中所有的图都是简单图,没有定义的术语和记号均可在[1]中找到.我们的主要结果是,用     

无爪图上团横贯数的界

设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.     

有关循环图C(n;{1,k})的独立数的一些结果

令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值.     

A proof on cycles and matching in balanced bipartite graphs

证明了对于二部图G=(V1,V2; E),|V1|=|V2|=n,如果满足δ(G)≥([1/2n])+1,则图G有一个生成子图,该子图包含指定长度的圈C和对集M,其中V(C)∩ V(M)=(空集).     

包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

关于图因子的邻集条件

设F为图G的一个支撑子图.如果对所有x∈V(G),有d_F(x)∈{1,3,…,2n-1),则称F为G的一个(1,3,…,2n-1)一因子;如果对所有x∈V(G),有d_F(x)=k,则称F为G的一个k-因子.本文以图的顶点邻集对一个图具有包含任一条给定边的{1,3,…,2n-1)-因子和k-因子分别给出了充分条件.     

关于树的完美邻域集与无冗余集 (英)

本文首先给出了求树图T的完美邻域的多项式时间复杂度算法(A),并在此基础上证明了当S是T的任一完美邻域且｜S｜=θ(T),则S是T的一极大无冗余集．然后给出了由T的一极大无冗余集生成完美邻域集的多项式时间复杂度算法(B),并依此算法证明了若S为T的任一极大无冗余集,则T存在一独立完美邻域集U且｜U｜≤｜S｜．     

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.     

Maximal independent sets in bipartite graphs

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order n and the extremal graphs as well as the corresponding results for connected bipartite graphs. © 1993 John Wiley & Sons, Inc.     

Tutte sets in graphs I: Maximal tutte sets and D‐graphs

A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency of G. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph G. Towards this end, we introduce a related graph D(G). We first show that the maximal Tutte sets in G are precisely the maximal independent sets in its D‐graph D(G), and then continue with the study of D‐graphs in their own right, and of iterated D‐graphs. We show that G is isomorphic to a spanning subgraph of D(G), and characterize the graphs for which G?D(G) and for which D(G)?D²(G). Surprisingly, it turns out that for every graph G with a perfect matching, D³(G)?D²(G). Finally, we characterize bipartite D‐graphs and comment on the problem of characterizing D‐graphs in general. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 343–358, 2007     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

The complexity of dissociation set problems in graphs

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.     

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.     

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

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

On Domination and Independence Numbers of Graphs

A set S of vertices of a graph G is dominating if each vertex x not in S is adjacent to some vertex in S, and is independent if no two vertices in S are adjacent. The domination number, γ(G), is the order of the smallest dominating set in G. The independence number, α(G), is the order of the largest independent set in G. In this paper we characterize bipartite graphs and block graphs G for which γ(G) = α(G).     

无爪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.