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

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

On Some Cycles in Wenger Graphs

Let p be a prime, q be a power of p, and let Fq be the field of q elements. For any positive integer n,the Wenger graph Wn(q) is defined as follows: it is a bipartite graph with the vertex partitions being two copies of the(n+1)-dimensional vector space Fqn+1, and two vertices p =(p(1), ···, p(n+1)) and l = [l(1), ···, l(n+1)]being adjacent if p(i) + l(i) = p(1)l(1)^i-1, for all i = 2, 3, ···, n + 1.In 2008, Shao, He and Shan showed that for n ≥ 2, Wn(q) contains a cycle of length 2 k ...     

变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．     

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

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.     

广义Petersen图的宽直径

广义Petersen图是一类重要的并被广泛研究的互连网络。本文证明了广义Petersen图 P(m,2)的直径和3宽直径分别为O(m/4)和O(m/3)。     

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     

二部定向图的最长通路和圈

Let D be a bipartite oriented graph in which the indegree and outdegree of each vertex are at least k. The result given in this paper is that D contains either a cycle of length at least 4k or a path of length at least 4k + 1. Jackson [1] declared that: if |V(D) |≤4k,D contains a Hamiltonian cycle. Evidently, the result Of this paper implies the result given by Jackson.     

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个圈点不相交.