Long dominating cycles and paths in graphs with large neighborhood unions

Let G be a graph of order n and define NC(G) = min{|N(u) ∪ N(v)| |uv ? E(G)}. A cycle C of G is called a dominating cycle or D-cycle if V(G) - V(C) is an independent set. A D-path is defined analogously. The following result is proved: if G is 2-connected and contains a D-cycle, then G contains a D-cycle of length at least min{n, 2NC(G)} unless G is the Petersen graph. By combining this result with a known sufficient condition for the existence of a D-cycle, a common generalization of Ore's Theorem and several recent “neighborhood union results” is obtained. An analogous result on long D-paths is also established.     

Long paths and cycles in oriented graphs

We obtain several sufficient conditions on the degrees of an oriented graph for the existence of long paths and cycles. As corollaries of our results we deduce that a regular tournament contains an edge-disjoint Hamilton cycle and path, and that a regular bipartite tournament is hamiltonian.     

Long paths and cycles in tough graphs

For a graphG, letp(G) andc(G) denote the length of a longest path and cycle, respectively. Let (t,n) be the minimum ofp(G), whereG ranges over allt-tough connected graphs onn vertices. Similarly, let (t,n) be the minimum ofc(G), whereG ranges over allt-tough 2-connected graphs onn vertices. It is shown that for fixedt>0 there exist constantsA, B such that (t,n)A·log(n) and (t,n)·log((t,n))B·log(n). Examples are presented showing that fort1 there exist constantsA, B such that (t,n)A·log(n) and (t,n)B· log(n). It is conjectured that (t,n) B·log(n) for some constantB. This conjecture is shown to be valid within the class of 3-connected graphs and, as conjectured in Bondy [1] forl=3, within the class of 2-connectedK _1.l-free graphs, wherel is fixed.     

赋权图中的路和圈

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

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

Long cycles in graphs without hamiltonian paths

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van den Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F. Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T. Yamashita, On relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree sums, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G)−c(G) at most 1 or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if , then p(G)−c(G)≤1, and (ii) if σ₄(G)≥n+3, then p(G)−c(G)≤2.     

Long induced paths and cycles in Kneser graphs

We present some lower and upper bounds on the length of the maximum induced paths and cycles in Kneser graphs.     

Long paths and cycles in random subgraphs of graphs with large minimum degree

For a given finite graph G of minimum degree at least k, let G_p be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if for a function that tends to infinity as k does, then G_p asymptotically almost surely contains a cycle (and thus a path) of length at least , and (ii) if , then G_p asymptotically almost surely contains a path of length at least k. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k + 1 vertices. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015     

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.     

Edge-disjoint paths and cycles in n-edge-connected graphs

We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n-edge-connected graph, s₁, ?,s_k, t₁, ?,t_k are vertices of G, and f₁, ?,f_l, g₁, ?,g_l, are pairwise distinct edges of G, then for each i = 1, ?, k there exists a path P_i in G, connecting s_i and t_i and for each i = 1, ?,l there exists a cycle C_i in G containing f_i and g_i such that P₁, ?,P_k, C₁, ?, C_l are pairwise edge-disjoint. We give upper and lower bounds for g(k, l).     

Long cycles in graphs with large degree sums and neighborhood unions

We present and prove several results concerning the length of longest cycles in 2-connected or 1-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings. © 1996 John Wiley & Sons, Inc.     

Relative length of long paths and cycles in graphs with large degree sums

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.     

Long cycles in critical graphs

It is shown that any k‐critical graph with n vertices contains a cycle of length at least , improving a previous estimate of Kelly and Kelly obtained in 1954. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 193–196, 2000     

Long cycles in bipartite graphs

Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2.     

Long cycles in vertex-transitive graphs

We prove that every connected vertex-transitive graph on n ≥ 4 vertices has a cycle longer than (3n)^1/2. The correct order of magnitude of the longest cycle seems to be a very hard question.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

Longest paths and cycles in bipartite oriented graphs

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2), on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense.     

Parity theorems for paths and cycles in graphs

We extend an elegant proof technique of A. G. Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree has an even number of paths if and only if its order is a multiple of four. Our results have implications for generalized friendship graphs and their conjectured nonexistence.