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

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

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     

Local resilience of graphs

In this article, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property measures how much one has to change G (locally) to destroy . Estimating the resilience leads to many new and challenging problems. Here we focus on random and pseudorandom graphs and prove several sharp results. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Ore定理的推广

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

Hamiltonicity of random graphs produced by 2‐processes

Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2‐regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Survey on path and cycle embedding in some networks

To find a cycle (resp. path) of a given length in a graph is the cycle (resp. path) embedding problem. To find cycles of all lengths from its girth to its order in a graph is the pancyclic problem. A stronger concept than the pancylicity is the panconnectivity. A graph of order n is said to be panconnected if for any pair of different vertices x and y with distance d there exist xy-paths of every length from d to n. The pancyclicity or the panconnectivity is an important property to determine if the topology of a network is suitable for some applications where mapping cycles or paths of any length into the topology of the network is required. The pancyclicity and the panconnectivity of interconnection networks have attracted much research interest in recent years. A large amount of related work appeared in the literature, with some repetitions. The purpose of this paper is to give a survey of the results related to these topics for the hypercube and some hypercube-like networks.      

On low degree k-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian) if, for any sequence of k distinct vertices v₁,…,v_k of G, there exists a cycle (respectively, a hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability, and motivated by the fact that k-orderedness of a graph implies (k-1)-connectivity, they posed the question of the existence of low degree k-ordered hamiltonian graphs. We construct an infinite family of graphs, which we call bracelet graphs, that are (k-1)-regular and are k-ordered hamiltonian for odd k. This result provides the best possible answer to the question of the existence of low degree k-ordered hamiltonian graphs for odd k. We further show that for even k, there exist no k-ordered bracelet graphs with minimum degree k-1 and maximum degree less than k+2, and we exhibit an infinite family of bracelet graphs with minimum degree k-1 and maximum degree k+2 that are k-ordered for even k. A concept related to k-orderedness, namely that of k-edge-orderedness, is likewise strongly related to connectivity properties. We study this relation and give bounds on the connectivity necessary to imply k-(edge-)orderedness properties.     

Cayley图的一些新结果

本文介绍了新大图论研讨班１９９５年以来完成七与他人合作完成的关于Ｃａｙｌｅｙ图的结果,主要集中在Ｃａｙｌｅｙ图的同构和自同构,连通性和哈顿性及随机Ｃａｙｌｅｙ图的基本性质等问题上,文的最后蜀列了全面而详细的参考文献。