赋权图中的路和圈

本文研究了赋权图中的最长路和最长圈,将关于非赋权图中最长路和最长圈的一些结果推广到赋权图上.     

Long cycles passing through vertices in k‐connected graphs

In this article, we consider the following problem proposed by Locke and Zhang in 1991: Let G be a k‐connected graph with minimum degree d and X a set of m vertices on a cycle of G. For which values of m and k, with , must G have a cycle of length at least passing through X? Fujisawa and Yamashita solved this problem for the case and in 2008. We provide an affirmative answer to this problem for the case of and .     

赋权图中存在重圈的一个定理的新证明

给出了如下定理的一个新的简短的证明:若G是一个满足k≥2的k连通赋权图,则G或者包含一个权至少为2m/(k 1)的圈,或者包含一个Hamilton圈,如果以下条件成立:(1)任意k 1个相互独立的顶点的赋权度和至少为m;(2)在G的每个导出爪,导出修正爪和导出P4中,所有边的权都相等.     

Hamiltonian cycles in n‐extendable graphs

A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg_G x+deg_G y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002     

Cycles passing through k + 1 vertices in k‐connected graphs

In this article, we prove the following theorem. Let k ≥ 3 be an integer, G be a k‐connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min {2d,|V(G)|} passing through X. This result gives the positive answer to the Question posed by Locke [8]. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:179–190, 2008     

Vertex‐disjoint cycles containing specified vertices in a bipartite graph

A minimum degree condition is given for a bipartite graph to contain a 2‐factor each component of which contains a previously specified vertex. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 145–166, 2004     

Edge disjoint cycles through specified vertices

We give a sufficient condition for a simple graph G to have k pairwise edge‐disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G[W] be 2k‐connected, and that for any two vertices at distance two in G[W], at least one of the two has degree at least |V(G)|/2 + 2(k ? 1) in G. This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k = 1) and Li (where W = V(G)). A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X, Y. If G is 2k connected, then G contains k Hamilton cycles that are pairwise edge‐disjoint except for edges in G[Y]. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On degree sum conditions for long cycles and cycles through specified vertices

Let G be a graph. For S⊂V(G), let Δ_k(S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Δ₂(S)≥d for every independent set S of order κ(G)+1, then G has a cycle of length at least min{d,|V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Δ₂(S)≥|V(G)| for every independent set S of order κ(X)+1 in G[X], then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles.     

赋权图中重圈的Dirac型条件

In this paper we give a Dirac type condition for heavy cycles in a 3-connected weighted graph,reading that if d~w(v)≥d for all v∈V(G)\{x} and w(uz)=w(vz),when uz,vz∈E(G) and uv ■ E(G).Then G contains either an (x,y)-cycle of weight at least 2d or a Hamilton cycle.     

Heavy cycles in 2-connected triangle-free weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex v is called the weighted degree of v, denoted by dw(v). The weight of a cycle is defined as the sum of the weights of its edges. Fujisawa proved that if G is a 2-connected triangle-free weighted graph such that the minimum weighted degree of G is at least d, then G contains a cycle of weight at least 2d. In this paper, we proved that if G is a2-connected triangle-free weighted graph of even size such that dw(u) + dw(v) ≥ 2d holds for any pair of nonadjacent vertices u, v ∈ V(G), then G contains a cycle of weight at least 2d.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Degree sums for edges and cycle lengths in graphs

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference—the length of a longest cycle—of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = K_r,r with r = n/2. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 253–256, 1997     

Heavy fans, cycles and paths in weighted graphs of large connectivity

A set of paths joining a vertex y and a vertex set L is called (y,L)-fan if any two of the paths have only y in common, and its width is the number of paths forming it. In weighted graphs, it is known that the existence of heavy fan is useful to find a heavy cycle containing some specified vertices.In this paper, we show the existence of heavy fans with large width containing some specified vertices in weighted graphs of large connectivity, which is a weighted analogue of Perfect's theorem. Using this, in 3-connected weighted graphs, we can find heavy cycles containing three specified vertices, and also heavy paths joining two specified vertices containing two more specified vertices. These results extend the previous results in 2-connected weighted graphs to 3-connected weighted graphs.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Disjoint hamiltonian cycles in bipartite graphs

Let G=(X,Y) be a bipartite graph and define . Moon and Moser [J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163-165. MR 28 # 4540] showed that if G is a bipartite graph on 2n vertices such that , then G is hamiltonian, sharpening a classical result of Ore [O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55] for bipartite graphs. Here we prove that if G is a bipartite graph on 2n vertices such that , then G contains k edge-disjoint hamiltonian cycles. This extends the result of Moon and Moser and a result of R. Faudree et al. [R. Faudree, C. Rousseau, R. Schelp, Edge-disjoint Hamiltonian cycles, Graph Theory Appl. Algorithms Comput. Sci. (1984) 231-249].