Small embeddings for partial 5‐cycle systems

It has been conjectured that any partial 5‐cycle system of order u can be embedded in a 5‐cycle system of order v whenever v ≥ 3 u/ 2+1 and v ≡ 1 , 5 (mod 10) . The smallest known embeddings for any partial 5‐cycle system of order u is 10 u +5 . In this paper we significantly improve this result by proving that for any partial 5‐cycle system of order u ≥ 255 , there exists a 5‐cycle system of order at most (9 u +146) / 4 into which the partial 5‐cycle system of order u can be embedded. © 2011 Wiley Periodicals, Inc. J Combin Designs     

Completing the spectrum of almost resolvable cycle systems with odd cycle length

In this paper, we construct almost resolvable cycle systems of order $4k+1$ for odd $k\ge 11$. This completes the proof of the existence of almost resolvable cycle systems with odd cycle length. As a by-product, some new solutions to the Hamilton–Waterloo problem are also obtained.     

On the construction of odd cycle systems

Three obvious necessary conditions for the existence of a k-cycle system of order n are that if n > 1 then n ? k, n is odd, and 2k divides n(n ? 1). We show that if these necessary conditions are sufficient for all n satisfying k ? n < 3k then they are sufficient for all n. In particular, there exists a 15-cycle system of order n if and only if n ≡ 1, 15, 21, or 25 (mod 30), and there exists a 21-cycle system of order n if and only if n ≡ 1, 7, 15, or 21 (mod 42), n ≠ 7. 15.     

A conjecture on small embeddings of partial Steiner triple systems

A well‐known, and unresolved, conjecture states that every partial Steiner triple system of order u can be embedded in a Steiner triple system of order υ for all υ ≡ 1 or 3, (mod 6), υ ≥ 2u + 1. However, some partial Steiner triple systems of order u can be embedded in Steiner triple systems of order υ <2u + 1. A more general conjecture that considers these small embeddings is presented and verified for some cases. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 313–321, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10017     

Optimal embeddings of odd ladders into a hypercube

An embedding of a graph G into a hypercube of dimension k is called optimal if the number of vertices of G is greater than 2^k−1. A ladder is a special graph in which two paths of the same length are connected in such a way that each vertex of the first one is connected by a path – called a rung – to its corresponding vertex in the second one. We construct an optimal embedding for every ladder with rungs of odd sizes greater than 6 into a dense set of a hypercube.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

A bound on the chromatic number using the longest odd cycle length

It is known that for every integer k ≥ 4, each k‐map graph with n vertices has at most kn ? 2k edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for k = 4, 5. We also show that this bound is not tight for large enough k (namely, k ≥ 374); more precisely, we show that for every and for every integer , each k‐map graph with n vertices has at most edges. This result implies the first polynomial (indeed linear) time algorithm for coloring a given k‐map graph with less than 2k colors for large enough k. We further show that for every positive multiple k of 6, there are infinitely many integers n such that some k‐map graph with n vertices has at least edges. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 267–290, 2007     

A proof of Lindner's conjecture on embeddings of partial Steiner triple systems

Lindner's conjecture that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if and is proved. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 63–89, 2009     

Reconstructing pluricanonical embeddings of general k-gonal curves via odd theta-characteristics

Abstract Here we investigate r-canonical embeddings of general k-gonal curves of genus g from the point of view of Caporaso–Sernesi’s reconstruction procedure via odd theta-characteristics. Keywords: Theta-characteristic, general k-gonal curve, trigonal curve, pluricanonical embedding, Hilbert scheme Mathematics Subject Classification (2000): 14H50, 14N05     

Finding odd cycle transversals

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.     

Tight embeddings of partial quadrilateral packings

Let f(n;C₄) be the smallest integer such that, given any set of edge disjoint quadrilaterals on n vertices, one can extend it into a complete quadrilateral decomposition by including at most f(n;C₄) additional vertices. It is known, and it is easy to show, that . Here we settle the longstanding problem that .     

NP-completeness for minimizing maximum edge length in grid embeddings

Given an embedding f: G →$\text{Z}$² of a graph G in the two-dimensional lattice, let |f| be the maximum L₁ distance between points f(x) and f(y) where xy is an edge of G. Let B₂(G) be the minimum |f| over all embeddings f. It is shown that the determination of B₂(G) for arbitrary G is NP-complete. Essentially the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → $\text{Z}$ⁿ of G into the n-dimensional integer lattice for any fixed n ≥ 2.     

Small surface trades in triangular embeddings

We enumerate all possible trades which involve up to six faces of the face set of a triangular embedding of a simple connected graph. These are classified by the underlying combinatorial trade on the associated block design, and by the geometrical arrangement of the faces necessary to avoid creation of a pseudosurface in the trading operation. The relationship of each of these trades to surface orientability is also established.     

2-restricted extensions of partial embeddings of graphs

Let K be a subgraph of G. Suppose that we have a 2-cell embedding of K in some surface and that for each K-bridge in G, one or two simple embeddings in faces of K are prescribed. Obstructions for existence of extensions of the embedding of K to an embedding of G are studied. It is shown that minimal obstructions possess certain combinatorial structure that can be described in an algebraic way by means of forcing chains of K-bridges. The geometric structure of minimal obstructions is also described. It is shown that they have “millipede” structure that was observed earlier in some special cases (disc, Möbius band). As a consequence it is proved that if one is allowed to reroute the branches of K, one can obtain a subgraph K′ of G homeomorphic to K for which an obstruction of bounded branch size exists. The precise combinatorial and geometric structure of corresponding obstructions can be used to get a linear time algorithm for either finding an embedding extension or discovering minimal obstructions.