Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs I: Latin Square Constructions

In an earlier paper the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part I, we explore a connection between orthogonal latin squares and embeddings. A product construction is presented for building pairs of orthogonal latin squares such that one member of the pair has a certain hamiltonian property. These hamiltonian squares are then used to construct embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that and for every prime p. Moreover, it is shown that the latin square construction utilized to get hamilton cycle embeddings of can also be used to obtain triangulations of . Part II of this series covers the case for every prime p and applies these embeddings to obtain some genus results.     

Cycle Frames of Complete Multipartite Multigraphs ‐ III

For two graphs G and H their wreath product has vertex set in which two vertices and are adjacent whenever or and . Clearly, , where is an independent set on n vertices, is isomorphic to the complete m‐partite graph in which each partite set has exactly n vertices. A 2‐regular subgraph of the complete multipartite graph containing vertices of all but one partite set is called partial 2‐factor. For an integer λ, denotes a graph G with uniform edge multiplicity λ. Let J be a set of integers. If can be partitioned into edge‐disjoint partial 2‐factors consisting cycles of lengths from J, then we say that has a ‐cycle frame. In this paper, we show that for and , there exists a ‐cycle frame of if and only if and . In fact our results completely solve the existence of a ‐cycle frame of .     

Cycle Extensions in BIBD Block‐Intersection Graphs

A cycle C in a graph G is extendable if there is some other cycle in G that contains each vertex of C plus one additional vertex. A graph is cycle extendable if every non‐Hamilton cycle in the graph is extendable. A balanced incomplete block design, BIBD, consists of a set V of v elements and a block set of k‐subsets of V such that each 2‐subset of V occurs in exactly λ of the blocks of . The block‐intersection graph of a design is the graph having as its vertex set and such that two vertices of are adjacent if and only if their corresponding blocks have nonempty intersection. In this paper, we prove that the block‐intersection graph of any BIBD is cycle extendable. Furthermore, we present a polynomial time algorithm for constructing cycles of all possible lengths in a block‐intersection graph.     

Semiframes with Block Size Three and Odd Group Size

A ‐semiframe of type is a ‐GDD of type , , in which the collection of blocks can be written as a disjoint union where is partitioned into parallel classes of and is partitioned into holey parallel classes, each holey parallel class being a partition of for some . A ‐SF is a ‐semiframe of type in which there are p parallel classes in and d holey parallel classes with respect to . In this paper, we shall show that there exists a (3, 1)‐SF for any if and only if , , , and .     

Neighborhoods in Maximum Packings of 2Kn and Quadratic Leaves of Triple Systems

In this paper, two related problems are completely solved, extending two classic results by Colbourn and Rosa. In any partial triple system of , the neighborhood of a vertex v is the subgraph induced by . For (mod 3) with , it is shown that for any 2‐factor F on or vertices, there exists a maximum packing of with triples such that F is the neighborhood of some vertex if and only if , thus extending the corresponding result for the case where or 1 (mod 3) by Colbourn and Rosa. This result, along with the companion result of Colbourn and Rosa, leads to a complete characterization of quadratic leaves of λ‐fold partial triple systems for all , thereby extending the solution where by Colbourn and Rosa.     

Small Complete Caps from Singular Cubics

New families of complete caps in finite Galois spaces are obtained. For most pairs with and , they turn out to be the smallest known complete caps in . Our constructions rely on the bicovering properties of certain plane arcs contained in plane cubic curves with a cusp.     

The Existence and Construction of (K5∖e)‐Designs of Orders 27, 135, 162, and 216

The problem of the existence of a decomposition of the complete graph into disjoint copies of has been solved for all admissible orders n, except for 27, 36, 54, 64, 72, 81, 90, 135, 144, 162, 216, and 234. In this paper, I eliminate 4 of these 12 unresolved orders. Let Γ be a ‐design. I show that divides 2^k3 for some and that . I construct ‐designs by prescribing as an automorphism group, and show that up to isomorphism there are exactly 24 ‐designs with as an automorphism group. Moreover, I show that the full automorphism group of each of these designs is indeed . Finally, the existence of ‐designs of orders 135, 162, and 216 follows immediately by the recursive constructions given by G. Ge and A. C. H. Ling, SIAM J Discrete Math 21(4) (2007), 851–864.     

On Small Complete Arcs and Transitive ‐Invariant Arcs in the Projective Plane

Let q be an odd prime power such that q is a power of 5 or (mod 10). In this case, the projective plane admits a collineation group G isomorphic to the alternating group A₅. Transitive G‐invariant 30‐arcs are shown to exist for every . The completeness is also investigated, and complete 30‐arcs are found for . Surprisingly, they are the smallest known complete arcs in the planes , and . Moreover, computational results are presented for the cases and . New upper bounds on the size of the smallest complete arc are obtained for .     

Set Systems with L‐Intersections and k‐Wise L‐Intersecting Families

In this paper, by employing linear algebra methods we obtain the following main results:

• (i) Let and be two disjoint subsets of such that Suppose that is a family of subsets of such that for every pair and for every i. Then Furthermore, we extend this theorem to k‐wise L‐intersecting and obtain the corresponding result on two cross L‐intersecting families. These results show that Snevily's conjectures proposed by Snevily (2003) are true under some restricted conditions. This result also gets an improvement of a theorem of Liu and Hwang (2013).
• (ii) Let p be a prime and let and be two subsets of such that or and Suppose that is a family of subsets of [n] such that (1) for every pair (2) for every i. Then This result improves the existing upper bound substantially.

     

Decomposing Complete Equipartite Multigraphs into Cycles of Variable Lengths: The Amalgamation‐detachment Approach

Using the technique of amalgamation‐detachment, we show that the complete equipartite multigraph can be decomposed into cycles of lengths (plus a 1‐factor if the degree is odd) whenever there exists a decomposition of into cycles of lengths (plus a 1‐factor if the degree is odd). In addition, we give sufficient conditions for the existence of some other, related cycle decompositions of the complete equipartite multigraph .     

Finiteness Results in Triangle‐Free Quasi‐Symmetric Designs

Triangle‐free quasi‐symmetric 2‐ designs with intersection numbers ; and are investigated. Possibility of triangle‐free quasi‐symmetric designs with or is ruled out. It is also shown that, for a fixed x and a fixed ratio , there are only finitely many triangle‐free quasi‐symmetric designs. © 2012 Wiley Periodicals, Inc. J Combin Designs 00: 1‐6, 2012     

Skew Hadamard Difference Sets from Dickson Polynomials of Order 7

Skew Hadamard difference sets have been an interesting topic of study for over 70 years. For a long time, it had been conjectured the classical Paley difference sets (the set of nonzero quadratic residues in where ) were the only example in Abelian groups. In 2006, the first author and Yuan disproved this conjecture by showing that the image set of is a new skew Hadamard difference set in with m odd, where denotes the first kind of Dickson polynomials of order n and . The key observation in the proof is that is a planar function from to for m odd. Since then a few families of new skew Hadamard difference sets have been discovered. In this paper, we prove that for all , the set is a skew Hadamard difference set in , where m is odd and . The proof is more complicated and different than that of Ding‐Yuan skew Hadamard difference sets since is not planar in . Furthermore, we show that such skew Hadamard difference sets are inequivalent to all existing ones for by comparing the triple intersection numbers.     

Direct Constructions for General Families of Cyclic Mutually Nearly Orthogonal Latin Squares

Two Latin squares and , of even order n with entries , are said to be nearly orthogonal if the superimposition of L on M yields an array in which each ordered pair , and , occurs at least once and the ordered pair occurs exactly twice. In this paper, we present direct constructions for the existence of general families of three cyclic mutually orthogonal Latin squares of orders , , and . The techniques employed are based on the principle of Methods of Differences and so we also establish infinite classes of “quasi‐difference” sets for these orders.     

Group Divisible Covering Designs with Block Size 4: A Type of Covering Array with Row Limit

A k‐GDCD, group divisible covering design, of type is a triple , where V is a set of gu elements, is a partition of V into u sets of size g, called groups, and is a collection of k‐subsets of V, called blocks, such that every pair of elements in V is either contained in a unique group or there is at least one block containing it, but not both. This family of combinatorial objects is equivalent to a special case of the graph covering problem and a generalization of covering arrays, which we call CARLs. In this paper, we show that there exists an integer such that for any positive integers g and , there exists a 4‐GDCD of type which in the worst case exceeds the Schönheim lower bound by δ blocks, except maybe when (1) and , or (2) , , and or . To show this, we develop constructions of 4‐GDCDs, which depend on two types of ingredients: essential, which are used multiple times, and auxiliary, which are used only once in the construction. If the essential ingredients meet the lower bound, the products of the construction differ from the lower bound by as many blocks as the optimal size of the auxiliary ingredient differs from the lower bound.     

The Mendelsohn Triple Systems of Order 13

A triple cyclically contains the ordered pairs , , , and no others. A Mendelsohn triple system of order v, or , is a set V together with a collection of ordered triples of distinct elements from V, such that and each ordered pair with is cyclically contained in exactly λ ordered triples. By means of a computer search, we classify all Mendelsohn triple systems of order 13 with ; there are 6 855 400 653 equivalence classes of such systems.     

‐Relative Difference Sets and Their Representations

We show that every ‐relative difference set D in relative to can be represented by a polynomial , where is a permutation for each nonzero a. We call such an f a planar function on . The projective plane Π obtained from D in the way of M. J. Ganley and E. Spence (J Combin Theory Ser A, 19(2) (1975), 134–153) is coordinatized, and we obtain necessary and sufficient conditions of Π to be a presemifield plane. We also prove that a function f on with exactly two elements in its image set and is planar, if and only if, for any .     

Simple Signed Steiner Triple Systems

Let X be a v‐set, be a set of 3‐subsets (triples) of X, and be a partition of with . The pair is called a simple signed Steiner triple system, denoted by ST, if the number of occurrences of every 2‐subset of X in triples is one more than the number of occurrences in triples . In this paper, we prove that exists if and only if , , and , where and for , . © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 332–343, 2012     

Flag‐Transitive 2‐ Symmetric Designs with Sporadic Socle

Let be a nontrivial 2‐ symmetric design admitting a flag‐transitive, point‐primitive automorphism group G of almost simple type with sporadic socle. We prove that there are up to isomorphism six designs, and must be one of the following: a 2‐(144, 66, 30) design with or , a 2‐(176, 50, 14) design with , a 2‐(176, 126, 90) design with or , or a 2‐(14,080, 12,636, 11,340) design with .     

The small Kakeya sets in,a conic

A Kakeya set in the linear representation , a nonsingular conic, is the point set covered by a set of lines, one through each point of . In this article, we classify the small Kakeya sets in . The smallest Kakeya sets have size , and all Kakeya sets with weight less than are classified: there are approximately types.     

New i‐Perfect Cycle Decompositions via Vertex Colorings of Graphs

Generalizing a result by Buratti et al.[M. Buratti, F. Rania, and F. Zuanni, Some constructions for cyclic perfect cycle systems, Discrete Math 299 (2005), 33–48], we present a construction for i‐perfect k‐cycle decompositions of the complete m‐partite graph with parts of size k. These decompositions are sharply vertex‐transitive under the additive group of with R a suitable ring of order m. The construction works whenever a suitable i‐perfect map exists. We show that for determining the set of all triples for which such a map exists, it is crucial to calculate the chromatic numbers of some auxiliary graphs. We completely determine this set except for one special case where is the product of two distinct primes, is even, and . This result allows us to obtain a plethora of new i‐perfect k‐cycle decompositions of the complete graph of order (mod 2k) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that .