Packing tight Hamilton cycles in 3‐uniform hypergraphs

Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ? H is a collection of n edges for which there is an ordering of the vertices v₁,…,v_n such that every triple of consecutive vertices {v_i,v_i+1,v_i+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Zero‐sum flows in designs

Let D be a t ‐ ( v, k , λ) design and let N _i (D) , for 1 ≤ i ≤ t , be the higher incidence matrix of D , a ( 0 , 1 )‐matrix of size , where b is the number of blocks of D . A zero‐sum flow of D is a nowhere‐zero real vector in the null space of N ₁ ( D ). A zero‐sum k‐flow of D is a zero‐sum flow with values in { 1 , …, ±( k ? 1 )}. In this article, we show that every non‐symmetric design admits an integral zero‐sum flow, and consequently we conjecture that every non‐symmetric design admits a zero‐sum 5‐flow. Similarly, the definition of zero‐sum flow can be extended to N _i ( D ), 1 ≤ i ≤ t . Let be the complete design. We conjecture that N _t ( D ) admits a zero‐sum 3‐flow and prove this conjecture for t = 2 . © 2011 Wiley Periodicals, Inc. J Combin Designs 19:355‐364, 2011     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

The chromatic index of graphs of even order with many edges

We show that, for r = 1, 2, a graph G with 2n + 2 (≥6) vertices and maximum degree 2n + 1 - r is of Class 2 if and only if |E(G/v)| > () - rn, where v is a vertex of G of minimum degree, and we make a conjecture for 1 ≤ r ≤ n, of which this result is a special case. For r = 1 this result is due to Plantholt.     

Quasi‐embeddings of Steiner triple systems,or Steiner triple systems of different orders with maximum intersection

In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u, v ≡ 1,3 (mod 6), u < v < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , where |?| = r. In other words, in order to “quasi‐embed” an STS(u) into an STS(v), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity (u(u ? 1)/6) ? r as the maximum intersection of an STS(u) and an STS(v) with u < v. We conjecture that the necessary minimum r = (v ? u) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t for t ≠ 2, or r = 7 when t = 2. Using small examples and recursion, we solve the cases v ? u = 2 and 4, asymptotically solve the cases v ? u = 6, 8, and 10, and further show for given v ? u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v ? u). Some results are obtained for v close to 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

Perfect fractional matchings in random hypergraphs

Given an r-uniform hypergraph H = (V, E) on |V| = n vertices, a real-valued function f:E→R⁺ is called a perfect fractional matching if Σ_vϵe f(e) ≤ 1 for all vϵV and Σ_eϵE f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n→ infinity, at the very moment t₀ when the last isolated vertex disappears, the hypergraph H_t0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (ln n + w(n))/ , where w(n) is any function tending to infinity with n, then with probability tending to 1 a random r-uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r-partite hypergraphs. © 1996 John Wiley & Sons, Inc.     

Resolvable packings of Kv with K2 × Kc's

The study of resolvable packings of K_v with K_r × K_c's is motivated by the use of DNA library screening. We call such a packing a (v, K_r × K_c, 1)‐RP. As usual, a (v, K_r × K_c, 1)‐RP with the largest possible number of parallel classes (or, equivalently, the largest possible number of blocks) is called optimal. The resolvability implies v ≡ 0 (mod rc). Let ρ be the number of parallel classes of a (v, K_r × K_c, 1)‐RP. Then we have ρ ≤ ?(v‐1)/(r + c ? 2)?. In this article, we present a number of constructive methods to obtain optimal (v, K₂ × K_c, 1)‐RPs meeting the aforementioned bound and establish some existence results. In particular, we show that an optimal (v, K₂ × K₃, 1)‐RP meeting the bound exists if and only if v ≡ 0 (mod 6). © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 177–189, 2009     

The size of minimum 3‐trees

A 3‐uniform hypergraph (3‐graph) is said to be tight, if for any 3‐partition of its vertex set there is a transversal triple. We give the final steps in the proof of the conjecture that the minimum number of triples in a tight 3‐graph on n vertices is exactly . © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 103–114, 2007     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

Decomposing <Emphasis Type="Italic">k</Emphasis>-ARc-Strong Tournaments Into Strong Spanning Subdigraphs

  The so-called Kelly conjecture states that every regular tournament on 2k+1 vertices has a decomposition into k-arc-disjoint hamiltonian cycles. In this paper we formulate a generalization of that conjecture, namely we conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. We prove several results which support the conjecture:If D = (V, A) is a 2-arc-strong semicomplete digraph then it contains 2 arc-disjoint spanning strong subdigraphs except for one digraph on 4 vertices.Every tournament which has a non-trivial cut (both sides containing at least 2 vertices) with precisely k arcs in one direction contains k arc-disjoint spanning strong subdigraphs. In fact this result holds even for semicomplete digraphs with one exception on 4 vertices.Every k-arc-strong tournament with minimum in- and out-degree at least 37k contains k arc-disjoint spanning subdigraphs H ₁, H ₂, . . . , H _k such that each H _i is strongly connected.The last result implies that if T is a 74k-arc-strong tournament with speci.ed not necessarily distinct vertices u ₁, u ₂, . . . , u _k , v ₁, v ₂, . . . , v _k then T contains 2k arc-disjoint branchings where is an in-branching rooted at the vertex u _i and is an out-branching rooted at the vertex v _i , i=1,2, . . . , k. This solves a conjecture of Bang-Jensen and Gutin [3].We also discuss related problems and conjectures.

On the diameter of i‐center in a graph without long induced paths

A graph G is said to be P_t‐free if it does not contain an induced path on t vertices. The i‐center C_i(G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, ⌊t/2⌋ ≤ i ≤ t − 2, with the property that, in every connected P_t‐free graph G, the i‐center C_i(G) of G induces a connected subgraph of G. In this article, the sharp upper bound on the diameter of G[C_i(G)] is established for every i ∈ I(t). The sharp lower bound on I(t) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999     

Retracts of box products with odd‐angulated factors

Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G□ H is S□T where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G□ H is S□T where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gⁿ is a core for all positive integers n, or the core of Gⁿ is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gⁿ is a core for any positive integer n. On the other hand, let G_i be a (2κ_i+1)‐angulated core for 1 ≤ i≤ n where κ₁ < κ₂ < … < κ_n. If G_i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n‐1, or G_i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n‐1, then □_i=1ⁿ G_i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C_2l+1 is a core for any integers l ≥ r ≥ 2. It is open whether K(r,2r+1) □ C_2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Packing of graphic n‐tuples

An n‐tuple π (not necessarily monotone) is graphic if there is a simple graph G with vertex set {v₁, …, v_n} in which the degree of v_i is the ith entry of π. Graphic n‐tuples (d, …, d) and (d, …, d) pack if there are edge‐disjoint n‐vertex graphs G₁ and G₂ such that d(v_i) = d and d(v_i) = d for all i. We prove that graphic n‐tuples π₁ and π₂ pack if , where Δand δdenote the largest and smallest entries in π₁ + π₂ (strict inequality when δ = 1); also, the bound is sharp. Kundu and Lovász independently proved that a graphic n‐tuple π is realized by a graph with a k‐factor if the n‐tuple obtained by subtracting k from each entry of π is graphic; for even n we conjecture that in fact some realization has k edge‐disjoint 1‐factors. We prove the conjecture in the case where the largest entry of π is at most n/2 + 1 and also when k?3. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Coloring uniform hypergraphs with few edges

A hypergraph is b‐simple if no two distinct edges share more than b vertices. Let m(r, t, g) denote the minimum number of edges in an r‐uniform non‐t‐colorable hypergraph of girth at least g. Erd?s and Lovász proved that A result of Szabó improves the lower bound by a factor of r^2?? for sufficiently large r. We improve the lower bound by another factor of r and extend the result to b‐simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed b, t, and ? > 0 and sufficiently large r, every r‐uniform b‐simple hypergraph with maximum edge‐degree at most t^rr^1?? is t‐colorable. Some results hold for list coloring, as well. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012