Search

A chord is an edge between two vertices of a cycle that is not an edge on the cycle. If a cycle has at least one chord, then the cycle is called a chorded cycle, and if a cycle has at least two chords, then the cycle is called a doubly chorded cycle. The minimum degree and the minimum degree-sum conditions are given for a graph to contain vertex-disjoint chorded (doubly chorded) cycles containing specified elements of the graph, i.e., specified vertices, specified edges as cycle-edges, specified paths, or specified edges as chords. Furthermore, the minimum degree condition is given for a graph to be partitioned into chorded cycles containing specified edges as cycle-edges.

Let G be a simple $$m\times m$$m×m bipartite graph with minimum degree $$\delta (G)\ge m/2+1$$?(G)?m/2+1. We prove that for every pair of vertices x, y, there is a Hamiltonian cycle in G such that the distance between x and y along that cycle equals k, where $$2\le k

Let H be a graph. A graph G is uniquely H-saturated if G contains no subgraph isomorphic to H, but for every edge e in the complement of G (i.e., for each "nonedge" of G), $$G+e$$G+e contains exactly one subgraph isomorphic to H. The double star$$D_{s,t}$$Ds,t is the graph formed by beginning with $$K_2$$K2 and adding $$s+t$$s+t new vertices, making s of these adjacent to one endpoint of the $$K_2$$K2 and the other t adjacent to the other endpoint; $$D_{s,s}$$Ds,s is a balanced double star. Our main result is that the trees T for which there exist an infinite number of uniquely T-saturated graphs are precisely the balanced double stars. In addition we completely characterize uniquely tree-saturated graphs in the case where the tree is a star $$K_{1,t} = D_{0, t-1}$$K1,t=D0,t-1. We show that if T is a double star, then there exists a nontrivial uniquely T-saturated graph. We conjecture that the converse holds; we verify this conjecture for all trees of order at most 6. We conclude by giving some open problems.

Given a fixed positive integer k ≥ 2, let G be a simple graph of order n ≥ 6k. It is proved that if the minimum degree of G is at least n/2 + 1, then for every pair of vertices x and y, there exists a Hamiltonian cycle such that the distance between x and y along that cycle is precisely k.

An upper bound on the saturation number for graphs as well as associated extremal graphs was given by (Kaszonyi and Tuza in J. Graph Theory, 10:203---210, 1986). A minor improvement of that result, which was implied in their paper, will be stated. Using this result, a series of exact saturation numbers and associated extremal graphs will be proved for the nearly complete graphs K t ? E(L), where L is a graph of order at most 4.

Given positive integers k ≤ m ≤ n, a graph G of order n is (k, m)-pancyclic ordered if for any set of k vertices of G and any integer r with m ≤ r ≤ n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k, m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided.

It will be shown that if G is a graph of order n which contains a triangle, a cycle of length n or n−1 and at least cn odd cycles of different lengths for some positive constant c, then there exists some positive constant k=k(c) such that G contains at least kn 1/6 even cycles of different lengths. Other results on the number of even cycle lengths which appear in graphs with many different odd length cycles will be given.

Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5].

In the study of hamiltonian graphs, many well known results use degree conditions to ensure sufficient edge density for the existence of a hamiltonian cycle. Recently it was shown that the classic degree conditions of Dirac and Ore actually imply far more than the existence of a hamiltonian cycle in a graph G, but also the existence of a 2-factor with exactly k cycles, where . In this paper we continue to study the number of cycles in 2-factors. Here we consider the well-known result of Moon and Moser which implies the existence of a hamiltonian cycle in a balanced bipartite graph of order 2n. We show that a related degree condition also implies the existence of a 2-factor with exactly k cycles in a balanced bipartite graph of order 2n with .

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graphG has orderp and minimum degree at least $$\frac{p}{2}$$ thenG is hamiltonian. Moon and Moser showed that a balanced bipartite graph (the two partite sets have the same order)G has orderp and minimum degree more than $$\frac{p}{4}$$ thenG is hamiltonian. In this paper, their idea is generalized tok-partite graphs and the following result is obtained: LetG be a balancedk-partite graph with orderp = kn. If the minimum degree $$\delta (G) > \left\{ {\begin{array}{*{20}c} {\left( {\frac{k}{2} - \frac{1}{{k + 1}}} \right)n if k is odd } \\ {\left( {\frac{k}{2} - \frac{2}{{k + 2}}} \right)n if k is even} \\ \end{array} } \right.$$ thenG is hamiltonian. The result is best possible.

We prove (a generalization of) the following conjecture of R. Haggkvist: LetG be a 2-connected graph onn vertices where every pair of nonadjacent vertices has degree sum at leastn — k and assume thatG has ak-factor; thenG is hamiltonian. This result is a common generalization of well-known theorems of Ore and Jackson, respectively.

LetG be a graph satisfying x(G) = k. The following problem is considered: WhichG have the property that, if n is large enough, the Ramsey numberr(G, T) has the value (k -- 1)(n -- 1) + 1 for all treesT onn vertices? It is shown thatG has this property if and only if for somem, G is a subgraph of bothL k,m andM K.m , whereL k,m andM k,m are two particulark-chromatic graphs. Indeed, it is shown thatr(L k,m ,M k,m ,T n ) = (k -- 1)(n -- 1) + 1 whenn is large.

A graphG with at least 2k vertices isk-path pairable if for anyk pairs of distinct vertices ofG there arek edge disjoint paths between the pairs. It will be shown for any positive integerk that there is ak-path pairable graph of maximum degree three.

Given positive integers k≤m≤n, a graph G of order n is (k,m)-pancyclic if for any set of k vertices of G and any integer r with m≤r≤n, there is a cycle of length r containing the k vertices. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply a graph is (k,m)-pancylic are proved. If the additional property that the k vertices must appear on the cycle in a specified order is required, then the graph is said to be (k,m)-pancyclic ordered. Minimum degree conditions and minimum sum of degree conditions for nonadjacent vertices that imply a graph is (k,m)-pancylic ordered are also proved. Examples showing that these constraints are best possible are provided.

A connected graphG is said to beF-good if the Ramsey numberr(F, G) is equal to(x(F) ? 1)(p(G) ? 1) + s(F), wheres(F) is the minimum number of vertices in some color class under all vertex colorings by ? (F) colors. It is of interest to know which graphsF have the property that all trees areF-good. It is shown that any large tree isK(1, 1,m 1,m 2,...,m t )-good.