Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

Dense Minors In Graphs Of Large Girth

We show that a graph of girth greater than 6 log k+3 and minimum degree at least 3 has a minor of minimum degree greater than k. This is best possible up to a factor of at most 9/4. As a corollary, every graph of girth at least 6 log r+3 log log r+c and minimum degree at least 3 has a K _r minor.     

Greedy maximum-clique decompositions

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. We have recently shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. A greedy max-clique decomposition is a particular kind cf greedy clique decomposition where maximum cliques are removed, instead of just maximal ones. In this paper, we show that any greedy max-clique decompositionC of a graph of ordern has, wheren(C) is the number of vertices inC.     

A generalization of Dirac’s theorem for K(1,3)-free graphs

It is known that if a 2-connected graphG of sufficiently large ordern satisfies the property that the union of the neighborhoods of each pair of vertices has cardinality at leastn/2, thenG is hamiltonian. In this paper, we obtain a similar generalization of Dirac’s Theorem forK(1,3)-free graphs. In particular, we show that ifG is a 2-connectedK(1,3)-free graph of ordern with the cardinality of the union of the neighborhoods of each pair of vertices at least (n+1)/3, thenG is hamiltonian. We also investigate several other related properties inK(1,3)-free graphs such as traceability, hamiltonian-connectedness, and pancyclicity. Partially Supported by O. N. R. Contract Number N00014-88-K-0070. Partially Supported by O. N. R. Contract Number N00014-85-K-0694.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Smallest maximally nonhamiltonian graphs

A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inG ^c, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n) 3/2 n forn 7. We exhibit graphs of even ordern 36 for which the bound is attained. These graphs are the snarks,J _k, of Isaacs and mild variations of them. For oddn 55 we construct graphs from the graphsJ _k showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJ _k, k 7 are hypohamiltonian cubics with girth 6.     

Girths of bipartite sextet graphs

An explicit construction of Biggs and Hoare yields an infinite family of bipartite cubic graphs. We prove that the ordern and girthg of each of these graphs are related by log₂ n<3/4·g+3/2.     

Simple minimum coverings ofK n with copies ofK 4 −e

Summary AK ₄–e design of ordern is a pair (S, B), whereB is an edge-disjoint decomposition ofK _n (the complete undirected graph onn vertices) with vertex setS, into copies ofK ₄–e, the graph on four vertices with five edges. It is well-known [1] thatK ₄–e designs of ordern exist for alln 0 or 1 (mod 5),n 6, and that if (S, B) is aK ₄–e design of ordern then |B| =n(n – 1)/10.Asimple covering ofK _n with copies ofK ₄–e is a pair (S, C) whereS is the vertex set ofK _n andC is a collection of edge-disjoint copies ofK ₄–e which partitionE(K_n)P, for some . Asimple minimum covering ofK _n (SMCK _n) with copies ofK ₄–e is a simple covering whereP consists of as few edges as possible. The collection of edgesP is called thepadding. Thus aK ₄–e design of ordern isSMCK _n with empty padding.We show that forn 3 or 8 (mod 10),n 8, the padding ofSMCK _n consists of two edges and that forn 2, 4, 7 or 9 (mod 10),n 9, the padding consists of four edges. In each case, the padding may be any of the simple graphs with two or four edges respectively. The smaller cases need separate treatment:SMCK ₅ has four possible paddings of five edges each,SMCK ₄ has two possible paddings of four edges each andSMCK ₇ has eight possible paddings of four edges each.The recursive arguments depend on two essential ingredients. One is aK ₄–e design of ordern with ahole of sizek. This is a triple (S, H, B) whereB is an edge-disjoint collection of copies ofK ₄–e which partition the edge set ofK _n\K_k, whereS is the vertex set ofK _n, and is the vertex set ofK _k. The other essential is acommutative quasigroup with holes. Here we letX be a set of size 2n 6, and letX = {x ₁, x₂, ..., x_n} be a partition ofX into 2-element subsets, calledholes of size two. Then a commutative quasigroup with holesX is a commutative quasigroup (X, ) such that for each holex _i X, (x_i, ) is a subquasigroup. Such quasigroups exist for every even order 2n 6 [4].     

Edge-isoperimetric inequalities in the grid

The grid graph is the graph on [k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. In this paper we give a lower bound for the number of edges between a subset of [k] ⁿ of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k] ⁿ of given cardinality. In particular, forr=1,...,k we show that ifA[k] ⁿ satisfies |A|r ⁿ then the subgraph of [k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097     

On the existence of two non-neighboring subgraphs in a graph

Does there exist a functionf(r, n) such that each graphG with _Z (G)≧f(r, n) contains either a complete subgraph of orderr or else two non-neighboringn-chromatic subgraphs? It is known thatf(r, 2) exists and we establish the existence off(r, 3). We also give some interesting results about graphs which do not contain two independent edges.     

Hypergraphs do not jump

The number α, 0≦α≦1, is a jump forr if for any positive ε and any integerm,m≧r, anyr-uniform hypergraph withn>n _o (ε,m) vertices and at least (α+ε) \(\left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)\) edges contains a subgraph withm vertices and at least (α+c) \(\left( {\begin{array}{*{20}c} m \\ r \\ \end{array} } \right)\) edges, wherec=c(α) does not depend on ε andm. It follows from a theorem of Erdös, Stone and Simonovits that forr=2 every α is a jump. Erdös asked whether the same is true forr≧3. He offered $ 1000 for answering this question. In this paper we give a negative answer by showing that \(1 - \frac{1}{{l^{r - 1} }}\) is not a jump ifr≧3,l>2r.     

Sparse color-critical hypergraphs

In this paper we obtain estimates for the least number of edges ann-uniformr-color-critical hypergraph of orderm may have.     

Random Minimum Length Spanning Trees in Regular Graphs

r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that . Received: Februray 9, 1998     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

A recursive construction of asymmetric 1-factorizations

W. D. Wallis has recently shown that forn 4, the complete graph on 2n points (denotedK _2n ) has two non-isomorphic 1-factorizations. In this paper we prove that forn 5,K _2n has a 1-factorization with no symmetry at all and that as n increases without bound, the number of pairwise non-isomorphic asymmetric 1-factorizations ofK _2n also increases without bound.The work of B. A. Anderson was partially supported by an Arizona State University Summer Faculty Fellowship.     

On a problem of Erdős and Rado

We give some improved estimates for the digraph Ramsey numbersr(K _n ^* ,L _m ), the smallest numberp such that any digraph of orderp either has an independent set ofn vertices or contains a transitive tournament of orderm. By results of Baumgartner and of Erdős and Rado, this is equivalent to the following infinite partition problem: for an infinite cardinal κ and positive integersn andm, find the smallest numberp such that

Symmetric designs with bruck subdesigns

IfP is a finite projective plane of ordern with a proper subplaneQ of orderm which is not a Baer subplane, then a theorem of Bruck [Trans. AMS 78(1955), 464–481] asserts thatn≧m ²+m. If the equalityn=m ²+m were to occur thenP would be of composite order andQ should be called a Bruck subplane. It can be shown that if a projective planeP contains a Bruck subplaneQ, then in factP contains a designQ′ which has the parameters of the lines in a three dimensional projective geometry of orderm. A well known scheme of Bruck suggests using such aQ′ to constructP. Bruck’s theorem readily extends to symmetric designs [Kantor, Trans. AMS 146 (1969), 1–28], hence the concept of a Bruck subdesign. This paper develops the analoque ofQ′ and shows (by example) that the analogous construction scheme can be used to find symmetric designs.     

Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

Diagonally implicit general linear methods for ordinary differential equations

We investigate some classes of general linear methods withs internal andr external approximations, with stage orderq and orderp, adjacent to the class withs=r=q=p considered by Butcher. We demonstrate that interesting methods exist also ifs+1=r=q, p=q orq+1,s=r+1=q, p=q orq+1, ands=r=q, p=q+1. Examples of such methods are constructed with stability function matching theA-acceptable generalized Padé approximations to the exponential function.The work of Z. Jackiewicz was partially supported by the National Science Foundation under grant NSF DMS-9208048.