图的上可嵌入性与独立顶点的度和

设G=（V,E）是2（或3）-边连通的简单图,独立数为α,围长为g,n=｜V｜.若下列条件之一成立：（1）独立数α＆lt;3g2（或6g-21）;（2）对G中任意含有m=3g2（或6g21）个顶点的独立集{v1,v2,...,vm}V,当g为偶数时,im=1dG（vi）n＋4（或n-11）;当g为奇数时,im=1dG（vi）n2（或n＋1）.则G是上可嵌入的.     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

图的上可嵌入性与围长及相邻顶点度和

$G$是一个阶为$n$围长为$g$的简单图, $u$和$v$是$G$中任意两个相邻顶点, 如果$d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 5$, 则$G$是上可嵌入的; 如果$G$是2-\!边连通(或3-\!边连通)图, 则当 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 3$ (或 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g - 5$)时$G$是上可嵌入的, 并且上面3个下界都是紧的.     

点度与图的上可嵌入性

本文证明了:(1) 设G是2-连通简单图,且不含K_3,若对任意一对距离为2的点u,u,有max{d(u),d(u)}>n/3-1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;(2) 设G是3-连通简单图,若对任意依次相邻的三点u,u,W,有max{d(u),d(u),d(w)}≥n/6+1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/6+1"是最好的.     

图的上可嵌入性与独立数、非邻节点度和

本文研究了图的上可嵌入性与独立数、非邻节度点和之间的关系,得到了一些新的上可嵌入图类,推广了—个相关结果.从而,为进一步研究图的上可嵌入性提供了一定的理论基础.     

顶点劈分与图的上可嵌入性（英文）

一个图G的弱子式G是通过对G进行边收缩得到的.一个弱子式封闭的上可嵌入图族是一个上可嵌入图的集合,并且该集合中任何图的弱子式仍在这个集合中.目前关于判断图的上可嵌入性的充要条件很少.本文通过研究顶点劈分与图的上可嵌入性的关系得出一个判断图的上可嵌入性的充要条件;给出了一个从环束出发构造弱子式封闭上可嵌入图族的方法;推广了[J.Graph Theory,1981,5(2):205-207]的一个结论.并且,用本文所得结论判断图的上可嵌入性时其算法复杂度会得到很大降低.     

图的上可嵌入性与非邻节点度和

本文得到了如下结果：令 Ｇ是一个 ２－边连通的（或３－边连通的）简单图，如果对于任何ｕｖ≠Ｅ（Ｇ）有则Ｇ是上可嵌入的．进而，这个下界是最好的．     

图的上可嵌入性

证明了一个连通无环图G如果能嵌入某个 (定向或不可定向 )曲面S上使得每个面的大小不超过 5 ,则G是上可嵌入的 .     

与顶点A-划分有关的上可嵌入图类

图G的顶点A-划分是指:G的顶点集划分{V1,V2,···,Vs},其中G[Vi](1≤i≤s)为多重完全图或多重完全二部图.文中结合图的顶点A-划分,顶点度及边连通性等条件确定了一些新的上可嵌入图类,从而将已有类似结果进行了推广,且完整地刻画了这类图的上可嵌入性情况.     

图的上可嵌入性的邻域条件

用NG（u）表示一个图G中任意点u的邻域集．本文主要证明了下述结果：设G是无环图,对G中任意相邻的点u和υ,即uυ∈E（G）,若如下两条件之一满足：（1）|NG(u)∩NG(υ)≥2;（2）G是2-点连通的图,且|NG(u)∩NG(υ)|≥1,则G是上可嵌入的．     

关于图的上可嵌入性的一个新的邻域条件

用NG(u)表示一个图G中任意点u的邻域集．L∈{K1．3,Kl，3 e}，其中K1．3,K1，3 e是G的点导出子图．本文主要证明了下述结果:设G是简单图，对L中任意两个距离为2的点u和v，即dL(u,v)=2，都有|NG(u)∩NG(v)|≥2，则G是上可嵌入的．特别地，每个L—free图是上可嵌入的．     

Upper Embeddability,Girth and the Degree-Sum of Nonadjacent Vertices

Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds

几类新的上可嵌入图

讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K_3,α(G)≤3,2)G为2-边连通的,且不含完全图K_3,α(G)≤5,3)G为3-边连通的,且不含完全图K_3,α(G)≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.     

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.     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

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

设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-哈密尔顿的和哈密尔顿连通的相关结果.     

用独立圈对图的一个划分

图G包含4k个点,k≥2,如果σ_2(G)≥4k,则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交.