独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

本质集的邻域并和图的哈密尔顿性

Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {Y1, Y2} 包含于Y such that dist (y1,y2)=2. In this paper, we use the technique of the vertex insertion on l-connected (l=k or k 1, k≥2) graphs to provide a unified proof for G to be hamiltonian, or hamiltonian-connected. The sufficient conditions are expressed an inequality on ∑i=1 K|N(Yi)| b|N(y0)| and n(Y) for each essential set Y={y0,y1,…,yk}, where b (1≤b≤k）is an integer,Yi={yi,yi-1,…,yi-(b-1}包含于Y\{y0} for i属于V（G):dist(v,Y)≤2}|.     

图的能量与哈密尔顿性

设G是一个无向简单图,A（G）为G的邻接矩阵．用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件：其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件．这些结果改进了一些已知的结果．     

图的能量与哈密尔顿性

设G是一个无向简单图, A(G)为$G$的邻接矩阵. 用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件; 其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件. 这些结果改进了一些已知的结果.     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

Ore定理的推广

设G是一个图,G的部分平方图G^*满足,公式见原文     

高度图的独立集复形

给定图G，称以G的所有独立集为单形的抽象复形I（G）为G的独立集复形．如果两个图G和H的独立集复形I（G）和I（H）的各阶同调群都是同构的，则称两个图是独立同调的．J（G）表示Gc的连通分支数，J3K2（G）表示Gc中同构于（3H2）c的连通分支数．本文研究了最小次δ（G）至少为其阶数|V（G）|减5的图G的独立集复形的结构，对满足δ（G）≥|V（C）|5，δ（H）≥|V（H）|－5的两个图G和H，（I）证明了，G和H独立同调的充要条件为J（G）＝J（H），J3K2（G）＝J3K2（H），且I（G）和I（H）的Euler示性数相同．（Ⅱ）给出了一个在图上计算I（G）的一维Betti数的方法，得到了一个I（G）是无圈复形的充要条件     

图的哈密尔顿性的谱条件(英文)

本文,我们利用补图的邻接矩阵的谱半径给出原图含有哈密尔顿路,哈密尔顿圈,以及原图是哈密尔顿-连通图的一些谱条件.     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。     

弦图的最大权强独立集

一、 引言 本文中未加说明的图论术语来自文献[1]。图G=(V,E)称为弦图,如果G的任何长度大于3的圈都有弦,或者等价地,任何长度大于3的圈都不会是G的点导出子图。本文中,子图总是指点导出子图,点子集S导出的G的子图记为G[S]。团是指完备子图,通常用它的点集来表示。如果图G的每个点v都带有点权w(v),则点子集S的权定义为S中点的权的和。     

The Neighborhood Union of Essential Sets and Hamiltonicity of Graphs

Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {y1,y2} (?) Y such that dist (y1,y2) = 2. In this paper, we use the technique of the vertex insertion on l-connected (l = k or k + 1, k≥ 2) graphs to provide a unified proof for G to be hamiltonian, or hamiltonian-connected. The sufficient conditions are expressed     

Tractable Partially Ordered Sets Derived from Root Systems and Biased Graphs

We study new posets Q obtained by removing from a geometric lattice L ofa biased graph certain flats indexed by a simplicial complex . (One example of L is the lattice of flats of thevector matroid of a root system B _n .) We study the structureand compute the characteristic polynomial of Q. With certainchoices of L and , including ones for which Q is alattice interpolating between those of B _n and D _n , we observe curious relationships among the roots of thecharacteristic polynomials of Q, L, and .     

Splittability for Partially Ordered Sets

A topological space X is said to be splittable over a class P of spaces if for every AX there exists continuous f:XYP such that f(A)f(XA) is empty. A class P of topological spaces is said to be a splittability class if the spaces splittable over P are precisely the members of P. We extend the notion of splittability to partially ordered sets and consider splittability over some elementary posets. We identify precisely which subsets of a poset can be split along over an n-point chain. Using these results it is shown that the union of two splittability classes need not be a splittability class and a necessary condition for P to be a splittability class is given.     

Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree

Galvin showed that for all fixed δ and sufficiently large n, the n‐vertex graph with minimum degree δ that admits the most independent sets is the complete bipartite graph . He conjectured that except perhaps for some small values of t, the same graph yields the maximum count of independent sets of size t for each possible t. Evidence for this conjecture was recently provided by Alexander, Cutler, and Mink, who showed that for all triples with , no n‐vertex bipartite graph with minimum degree δ admits more independent sets of size t than . Here, we make further progress. We show that for all triples with and , no n‐vertex graph with minimum degree δ admits more independent sets of size t than , and we obtain the same conclusion for and . Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree δ whose minimum degree drops on deletion of an edge or a vertex.     

偏序集最小顶点割算法与最小费用赶工问题

在网络计划问题中,一项大的工程由许多工序合成。工序与工序之间存在着一定的前后关系,每个工序有着自己的正常加工时间和通过赶工所能达到的最短加工时间以及每赶工一天的赶工费用。设一项工程的正常工期为T天,通过对所有可能的工序赶工,整个工程能达到的最短工期为S天。本文的问题是,对于任意给定的t(S t相似文献   

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.     

Quasi-shadowing Property on Random Partially Hyperbolic Sets

In this paper we investigate the quasi-shadowing property for C~1 random dynamical systems on their random partially hyperbolic sets. It is shown that for any pseudo orbit {xk}_(-∞)~(+∞)on a random partially hyperbolic set there exists a "center" pseudo orbit {yk}_(-∞)~(+∞)shadowing it in the sense that yk+1 is obtained from the image of yk by a motion along the center direction. Moreover, when the random partially hyperbolic set has a local product structure, the above "center" pseudo orbit {yk}_(-∞)~(+∞)can be chosen such that yk+1 and the image of yk lie in their common center leaf.     

Forbidden Pairs of Disconnected Graphs Implying Hamiltonicity

Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n₀ such that every 2‐connected ‐free graph of order at least n₀ is hamiltonian.