On the circumference of a graph and its complement

Let G be a graph of order n and circumference c(G). Let be the complement of G. We prove that and show sharpness of this bound.     

The complete closure of a graph

We define the complete closure number cc(G) of a graph G of order n as the greatest integer k ≤ 2n ? 3 such that the kth Bondy-Chvátal closure Cl_k(G) is complete, and give some necessary or sufficient conditions for a graph to have cc(G) = k. Similarly, the complete stability cs(P) of a property P defined on all the graphs of order n is the smallest integer k such that if Cl_k(G) is complete then G satisfies P. For some properties P, we compare cs(P) with the classical stability s(P) of P and show that cs(P) may be far smaller than s(P). © 1993 John Wiley & Sons, Inc.     

The size Ramsey number

Let denote the class of all graphsG which satisfyG(G ₁,G ₂). As a way of measuring minimality for members of, we define thesize Ramsey number (G ₁,G ₂) by.We then investigate various questions concerned with the asymptotic behaviour of.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

Locating Pairs of Vertices on a Hamiltonian Cycle in Bigraphs

Let G be a simple \(m\times m\) bipartite graph with minimum degree \(\delta (G)\ge 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<m/6\) is an integer having appropriate parity. We conjecture that this is also true up to \(k\le m\).     

Three-regular path pairable graphs

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.Research is partially supported by ONR research grant N000014-88-K-0070 and NAS Exchange grant.     

Strongly regular graphs and finite Ramsey theory

Some connections between strongly regular graphs and finite Ramsey theory are drawn. Let B_n denote the graph K₂+K?_n. If there exists a strongly regular graph with parameters (υ, k, λ, μ), then the Ramsey number r(B_λ+1, B_{υ?2k+μ ?1})?υ+1. We consider the implications of this inequality for both Ramsey theory and the theory of strongly regular graphs.     

Endpoint extendable paths in tournaments

Let s(n) be the threshold for which each directed path of order smaller than s(n) is extendible from one of its endpoints in some tournament T_n It is shown that s(n) is asymptotic to 3n/4, with an error term at most 3 for infinitely many n. There are six tournaments with s(n) = n. © 1996 John Wiley & Sons, Inc.     

Path-path Ramsey-type numbers for the complete bipartite graph

For a fixed pair of integers r, s ≥ 2, all positive integers m and n are determined which have the property that if the edges of K_m,n (a complete bipartite graph with parts n and m) are colored with two colors, then there will always exist a path with r vertices in the first color or a path with s vertices in the second color.     

Minimum Degree and Dominating Paths

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n‐vertex k‐connected graph and , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a). The preceding results are sharp. For constant s and , an s‐vertex dominating path is guaranteed by when n is sufficiently large, but (where ) does not even guarantee a dominating set of size s. We also obtain minimum‐degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.