On Resolvable Multipartite G-Designs II

In this paper, it has been proved that and are factorable, where ⊗ denotes wreath product of graphs. As a consequence, a resolvable (k,n,k,2λ) multipartite –design exists for even k. These results generalize the results of Ushio on –factorizations of complete tripartite graphs.     

The Maximum Size of 3-Wise Intersecting and 3-Wise Union Families

Let be an n-uniform hypergraph on 2n vertices. Suppose that and holds for all F₁,F₂,F₃ ∈ . We prove that the size of is at most . The second author was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027     

On the Circumference of 3-Connected Quasi-Claw-Free Graphs

A graph G is quasi-claw-free if it satisfies the property: d(x,y)=2 ⇒ there exists such that . In the paper, we prove that the circumference of a 3-connected quasi-claw-free graph G on n vertices is at least min{4δ−2,n} and G is hamiltonian if n≤5δ−5.     

On Cross-intersecting Families of Sets

A family of -element subsets and a family of k-element subsets of an n-element set are cross-intersecting if every set from has a nonempty intersection with every set from . We compare two previously established inequalities each related to the maximization of the product , and give a new and short proof for one of them. We also determine the maximum of for arbitrary positive weights ,_k.     

Bipartite Subgraphs and Quasi-Randomness

We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in G_n is at most (1+o(1))p^e(H)n^v(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs K_a,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003     

Colouring Cubic Graphs by Small Steiner Triple Systems

Given a Steiner triple system , we say that a cubic graph G is -colourable if its edges can be coloured by points of in such way that the colours of any three edges meeting at a vertex form a triple of . We prove that there is Steiner triple system of order 21 which is universal in the sense that every simple cubic graph is -colourable. This improves the result of Grannell et al. [J. Graph Theory 46 (2004), 15–24] who found a similar system of order 381. On the other hand, it is known that any universal Steiner triple system must have order at least 13, and it has been conjectured that this bound is sharp (Holroyd and Škoviera [J. Combin. Theory Ser. B 91 (2004), 57–66]). Research partially supported by APVT, project 51-027604. Research partially supported by VEGA, grant 1/3022/06.     

Minimal Connected τ-Critical Hypergraphs

A hypergraph is τ-critical if τ(−{E})<τ() for every edge E ∈ , where τ() denotes the transversal number of . We show that if is a connected τ-critical hypergraph, then −{E} can be partitioned into τ()−1 stars of size at least two, for every edge E ∈ . An immediate corollary is that a connected τ-critical hypergraph has at least 2τ()−1 edges. This extends, in a very natural way, a classical theorem of Gallai on colour-critical graphs, and is equivalent to a theorem of Füredi on t-stable hypergraphs. We deduce a lower bound on the size of τ-critical hypergraphs of minimum degree at least two.     

Consistent Cycles in Graphs and Digraphs

Let Γ be a finite digraph and let G be a subgroup of the automorphism group of Γ. A directed cycle of Γ is called G-consistent whenever there is an element of G whose restriction to is the 1-step rotation of . Consistent cycles in finite arc-transitive graphs were introduced by J. H. Conway in his public lectures at the Second British Combinatorial Conference in 1971. He observed that the number of G-orbits of G-consistent cycles of an arc-transitive group G is precisely one less than the valency of the graph. In this paper, we give a detailed proof of this result in a more general setting of arbitrary groups of automorphisms of graphs and digraphs. Supported in part by ``Ministrstvo za šolstvo, znanost in šport Republike Slovenije', bilateral project BI-USA/04-05/38.     

Spanning Trails Connecting Given Edges

Suppose that is the set of connected graphs such that a graph G if and only if G satisfies both (F1) if X is an edge cut of G with |X|3, then there exists a vertex v of degree |X| such that X consists of all the edges incident with v in G, and (F2) for every v of degree 3, v lies in a k-cycle of G, where 2k3.In this paper, we show that if G and (G)3, then for every pair of edges e,fE(G), G has a trail with initial edge e and final edge f which contains all vertices of G. This result extends several former results.     

On the Set of Cycle Lengths in a Hamiltonian Graph with a Given Maximum Degree

Let n and be two integers such that 2n–1. We describe the set of cycle lengths occurring in any hamiltonian graph G of order n and maximum degree . We conclude that for the case this set contains all the integers belonging to the union [3,2–n+2][n–+2,+1], and for it contains every integer between 3 and +1. We also study the set of cycle lengths in a hamiltonian graph with two fixed vertices of large degree sum. Our main results imply that the stability s(P) for the property of being pancyclic satisfies      

A Lower Bound for the Rectilinear Crossing Number

We give a new lower bound for the rectilinear crossing number of the complete geometric graph K_n. We prove that and we extend the proof of the result to pseudolinear drawings of K_n. Dedicated to the memory of our good friend and mentor Víctor Neumann-Lara. Received: April, 2003 Final version received: March 18, 2005     

Orthogonal Double Covers of Complete Graphs by Caterpillars of Diameter 5

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection = {G_i|i = 1,2, . . . ,n} of spanning subgraphs of K_n, all isomorphic to G, with the property that every edge of K_n belongs to exactly two members of and any two distinct members of share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K_n.     

Constructions of Quad-Rooted Double Covers

A collection of spanning subgraphs of K_n is called an orthogonal double cover if (i) every edge of K_n belongs to exactly two of the G_is and (ii) any two distinct G_is intersect in exactly one edge. Chung and West [3] conjectured that there exists an orthogonal double cover of K_n for all n, in which each G_i has maximum degree 2, and proved this result for n in six of the residue classes modulo 12. In [6], Gronau, Mullin and Schellenberg solved the conjecture. In addition to solving the conjecture, they went on to consider a problem for n 5 mod 6 such that each spanning subgraph G_i consists of the vertex-disjoint union of an isolated vertex, a quadrilateral, and triangles. They proved that for any n 2 mod 3 and n {8, 11, 38, 41, 44, 47, 50, 53, 59, 62, 71, 83, 86, 89, 95, 101, 107, 113, 122, 131, 143, 146, 149, 158, 164, 167, 173, 176, 179, 218, 242, 248, 287}, there exists a quad-rooted double cover of order n. In this note, we improve their result by showing that such designs exist for any n 2 mod 3 and n {8, 11, 38, 41, 44, 50, 53, 62, 71}.     

Ribbon tableaux and the Heisenberg algebra

In [LLT] Lascoux, Leclerc and Thibon introduced symmetric functions which are spin and weight generating functions for ribbon tableaux. This article is aimed at studying these functions in analogy with Schur functions. In particular we will describe: a Pieri and dual-Pieri formula for ribbon functions, a ribbon Murnaghan-Nakayama formula, ribbon Cauchy and dual Cauchy identities, and a -algebra isomorphism _n:(q)(q) which sends each to .Our study of the functions will be connected to the Fock space representation F of via a linear map :F(q) which sends the standard basis of F to the ribbon functions. Kashiwara, Miwa and Stern [KMS] have shown that a copy of the Heisenberg algebra H acts on F commuting with the action of . Identifying the Fock Space of H with the ring of symmetric functions (q) we will show that is in fact a map of H-modules with remarkable properties. The study of this map will lead to our identities concerning ribbon tableaux generating functions. We will also give a combinatorial proof that the ribbon Murnaghan-Nakayama and Pieri rules are formally equivalent.     

A Note on Convex Decompositions of a Set of Points in the Plane

For any set P of n points in general position in the plane there is a convex decomposition of P with at most elements. Moreover, any minimal convex decomposition of such a set P has at most elements, where k is the number of points in the boundary of the convex hull of P.Partially supported by Conacyt, MexicoFinal version received: November 10, 2003     

Extendable Cycles in Multipartite Tournaments

An n-partite tournament is an orientation of a complete n-partite graph. If D is a strongly connected n-partite (n3) tournament, then we shall prove that every partite set of D has at least one vertex which lies on a cycle C_m of each length m for such that V(C₃)V(C₄)V(C_n), where V(C_m) is the vertex set of C_m for . This result extends those of Bondy [2], Guo and Volkmann [4], Gutin [6], Moon [8], and Yeo [12].Final version received: June 9, 2003     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

Even 2 × 2 Submatrices of a Random Zero-One Matrix

Consider an m×n zero-one matrix A. An s×t submatrix of A is said to be even if the sum of its entries is even. In this paper, we focus on the case m=n and s=t=2. The maximum number M(n) of even 2×2 submatrices of A is clearly and corresponds to the matrix A having, e.g., all ones (or zeros). A more interesting question, motivated by Turán numbers and Hadamard matrices, is that of the minimum number m(n) of such matrices. It has recently been shown that for some constant B. In this paper we show that if the matrix A=A_n is considered to be induced by an infinite zero one matrix obtained at random, then where E_n denotes the number of even 2×2 submatrices of A_n. Results such as these provide us with specific information about the tightness of the concentration of E_n around its expected value of Acknowledgments. The research of both authors was supported by NSF Grant DMS-0139291 and conducted at East Tennessee State University during the Summer of 2002, when Johnson was a student in Godboles Research Experiences for Undergraduates Program. The valuable suggestions of two anonymous referees are gratefully acknowledged.     

The cofinality of the saturated uncountable random graph

Assuming CH, let be the saturated random graph of cardinality ₁. In this paper we prove that it is consistent that and can be any two prescribed regular cardinals subject only to the requirement