1-Pancyclic Hamilton Cycles in Random Graphs

We consider a generalization of the pancyclic property. A graph G is defined to be 1-pancyclic if there is some Hamilton cycle H in G such that we can find a cycle C_s of length s (3 ? s ? n ? 1) using only the edges of H and one other edge e_s. We show that the threshold for G_n,p to be Hamiltonian, is the threshold for the 1-pancyclic property.     

Hamilton Cycles in Implicit 2-Heavy Graphs

Let id(v) denote the implicit degree of a vertex v in a graph G. We define G of order n to be implicit 2-heavy if at least two of the end vertices of each induced claw have implicit degree at least \(\frac{n}{2}\). In this paper, we show that every implicit 2-heavy graph G is hamiltonian if we impose certain additional conditions on the connectivity of G or forbidden induced subgraphs. Our results extend two previous theorems of Broersma et al. (Discret Math 167–168:155–166, 1997) on the existence of Hamilton cycles in 2-heavy graphs.     

Some Properties of Graphs of Diameters

The main result of this paper is as follows. Any two cycles of odd lengths of the graph of diameters G in three-dimensional Euclidean space have a common vertex. Some properties of graphs of diameters in two-dimensional Banach spaces with strictly convex metrics are also established. Applications are given. Received December 28, 1998, and in revised form September 10, 1999. Online publication May 15, 2000.     

Neighborhood Unions and Hamilton Cycles in Bipartite Graphs

ＮｅｉｇｈｂｏｒｈｏｏｄＵｎｉｏｎｓａｎｄＨａｍｉｌｔｏｎＣｙｃｌｅｓｉｎＢｉｐａｒｔｉｔｅＧｒａｐｈｓＬｉｕＹｉｐｉｎｇ（刘一平）；ＷｕＺｈｅｎｇｓｈｅｎｇ（吴正声）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＮｏｒｍａｌＵｎｉ...     

关于图与圈之并图的圈唯一性

Farrell[1]引进图 G 的圈多项式 c(G;■).文[6]猜测:轮形图 W_8是圈唯一的.本文中我们证明上述猜测为真且讨论了某些图与圈之并图的圈唯一性.     

变更图的直径

对于给定的正整数t和d(≥2),用F(t,d)和P(t,d)分别表示在所有直径为d的图和路中添加t条边后得到的图的最小直径,用f(t, d)表示从所有直径为d的图中删去t条边后得到的图的最大直径. 已经证明P(1, d)=(d)/(2), P(2,d)=(d 1)/(3)和P(3, d)=(d 2)/(4). 一般地,当t和d≥4时有(d 1)/(t 1)-1≤P(t, d)≤(d 1)/(t 1) 3. 在这篇文章中,我们得到F(t, f(t, d))≤d≤f(t, F(t, d))和(d)/(t 1)≤F(t, d)=P(t, d)≤(d-2)/(t 1) 3,而且当d充分大时,F(t, d)≤(d)/(t) 1. 特别地,对任意正整数k有P(t, (2k-1)(t 1) 1)=2k,当t=4或5,且d≥4时有(d)/(t 1)≤P(t, d)≤(d)/(t 1) 1.     

Some Results on Weighted Graphs without Induced Cycles of Nonpositive Weights

Let G be a simple graph; assume that a mapping assigns integers as weights to the edges of G such that for each induced subgraph that is a cycle, the sum of all weights assigned to its edges is positive; let σ be the sum of weights of all edges of G. It has been proved (Vijayakumar, Discrete Math 311(14):1385–1387, 2011) that (1) if G is 2-connected and the weight of each edge is not more than 1, then σ is positive. It has been conjectured (Xu, Discrete Math 309(4):1007–1012, 2009) that (2) if the minimum degree of G is 3 and the weight of each edge is ±1, then σ > 0. In this article, we prove a generalization of (1) and using this, we settle a vast generalization of (2).     

Homomorphisms of Products of Graphs into Graphs Without Four Cycles

Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product). Received August 31, 1998/Revised April 19, 2000 RID="†" ID="†" Supported by NSERC of Canada Grant #691325.     

Cycles in Circuit Graphs of Matroids

Let G be the circuit graph of any connected matroid. We prove that G is edge-pancyclic if it has at least three vertices. This work is supported by the National Natural Science Foundation(60673047) and the Doctoral Program Foundation of Education Ministry (20040422004) of China.     

Homogeneous Embeddings of Cycles in Graphs

If G and H are vertex-transitive graphs, then the framing number fr(G,H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(C _m,C _n) for m<n. We show first that fr(C _m,C _n)≥n+2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(C _m,C _n) is approximately the minimum of and n+n/m. Received: June 12, 1996 / Revised: June 2, 1997     

Spanning Cyclic Subdivisions of Vertex-Disjoint Cycles and Chorded Cycles in Graphs

Let G be a graph on n ≥ 3 vertices and H be a subgraph of G such that each component of H is a cycle with at most one chord. In this paper we prove that if the minimum degree of G is at least n/2, then G contains a spanning subdivision of H such that only non-chord edges of H are subdivided. This gives a new generalization of the classical result of Dirac on the existence of Hamilton cycles in graphs.     

Domination Number of Graphs Without Small Cycles

It has been shown (J. Harant and D. Rautenbach, Domination in bipartite graphs. Discrete Math. 309:113–122, 2009) that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 nor 13 is at most \frac3n8{\frac{3n}{8}}. They believed that the assumption that the graphs do not contain cycles of length 10 might be replaced by the exclusion of finitely many exceptional graphs. In this paper, we positively answer that if G is a connected graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5 nor 7 and is not one of three exceptional graphs, then the domination number of G is at most \frac3n8{\frac{3n}{8}}.     

用独立圈对图的一个划分

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

Counting the Number of Hamilton Cycles in Random Digraphs

We show that there exists a a fully polynomial randomized approximation scheme for counting the number of Hamilton cycles in almost all directed graphs.     

Star网络S_5的Hamilton圈分解

最近Star网络和Pancake网络作为超立方体(并行计算机中多处理机互连的一种著名拓扑结构)的替代品而被许多作者研究.这两种网络的一个好的特点是:与超立方体相比较,它们有较小的直径和顶点度.尤其Star网络,更是受到研究人员的极大关注.在本文中:(a)我们提出了一种在这两种网络中找Hamilton圈的新方法.(b)证明了关于Star网络S_n的一个猜想在n=5时是正确的,即给出了S_5的两个边不交的Hamilton圈,且S_5是这两个Hamilton圈的并.     

Decomposition of Complete Graphs into Cycles and Stars

Let C _k denote a cycle of length k and let S _k denote a star with k edges. As usual K _n denotes the complete graph on n vertices. In this paper we investigate decomposition of K _n into C _l ’s and S _k ’s, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of K _n into p copies of C ₄ and q copies of S ₄ if and only if ${4(p + q)={n \choose 2}, q\ne 1}$ if n is odd, and ${q\geq max\{3, \lceil{\frac{n}{4}\rceil}\}}$ if n is even.     

K-Factors and Hamilton Cycles in Graphs

We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.     

圈和完全图的点可区别VE-全染色(英文)

Let G be a simple graph of order at least 2.A VE-total-coloring using k colors of a graph G is a mapping f from V (G) E(G) into {1,2,···,k} such that no edge receives the same color as one of its endpoints.Let C(u)={f(u)} {f(uv) | uv ∈ E(G)} be the color-set of u.If C(u)=C(v) for any two vertices u and v of V (G),then f is called a k-vertex-distinguishing VE-total coloring of G or a k-VDVET coloring of G for short.The minimum number of colors required for a VDVET coloring of G is denoted by χ ve vt (G) and it is called the VDVET chromatic number of G.In this paper we get cycle C n,path P n and complete graph K n of their VDVET chromatic numbers and propose a related conjecture.