Optimal holey packings OHP4(2, 4, n ,3)'s

An optimal holey packing OHP_d(2, k, n, g) is equivalent to a maximal (g + 1)‐ary (n, k, d) constant weight code. In this paper, we provide some recursive constructions for OHP_d(2, k, n, g)'s and use them to investigate the existence of an OHP₄(2, 4, n, 3) for n ≡ 2, 3 (mod 4). Combining this with Wu's result ( 18 ), we prove that the necessary condition for the existence of an OHP₄(2, 4, n, 3), namely, n ≥ 5 is also sufficient, except for n ∈ {6, 7} and except possibly for n = 26. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 111–123, 2006     

Existence of Generalized Steiner Systems <Emphasis Type="Italic">GS</Emphasis>(2,4,ν,2)

Generalized Steiner systems GS(2,4,v,2) were first discussed by Etzion and used to construct optimal constant weight codes over an alphabet of size three with minimum Hamming distance five, in which each codeword has length v and weight four. Etzion conjectured its existence for any integer v 7 and v 1(mod 3). The conjecture has been verified for prime powers v > 7 and v 7(mod 12) by the latter two of the present authors. It has also been pointed out that there does not exist a GS(2,4,7,2). In this paper, constructions using frame generalized Steiner systems, two holey perfect bases and orthogonal Latin squares are discussed. With these constructions the conjecture is confirmed with the exception for v=7 and three possible exceptions for v 13, 52, 58.AMS classification: 05B05, 94B25     

Constructions for generalized Steiner systems <Emphasis Type="Italic">GS</Emphasis>(3, 4, <Emphasis Type="Italic">v</Emphasis>, 2)

Generalized Steiner systems GS (3, 4, v, 2) were first discussed by Etzion and used to construct optimal constant weight codes over an alphabet of size three with minimum Hamming distance three, in which each codeword has length v and weight four. Not much is known for GS (3, 4, v, 2)s except for a recursive construction and two small designs for v = 8,10 given by Etzion. In this paper, more small designs are found by computer search and also given are direct constructions based on finite fields and rotational Steiner quadruple systems and recursive constructions using three-wise balanced designs. Some infinite families are also obtained.      

4‐*GDDs(3n) and generalized Steiner systems GS(2, 4, v, 3)

Generalized Steiner systems GS(2, k, v, g) were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 2k ? 3, in which each codeword has length v and weight k. As to the existence of a GS(2, k, v, g), a lot of work has been done for k = 3, while not so much is known for k = 4. The notion k‐*GDD was first introduced and used to construct GS(2, 3, v, 6). In this paper, singular indirect product (SIP) construction for GDDs is modified to construct GS(2, 4, v, g) via 4‐*GDDs. Furthermore, it is proved that the necessary conditions for the existence of a 4‐*GDD(3ⁿ), namely, n ≡ 0, 1 (mod 4) and n ≥ 8 are also sufficient. The known results on the existence of a GS(2, 4, v, 3) are then extended. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 381–393, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10047     

Generalized Steiner Systems GS(2, 4, v, 2) with v a Prime Power ≡ 7 (mod 12)

Generalized Steiner systems GS(2, 4, v, g) were first introduced by Etzion and were used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 5, in which each codeword has length v and weight 4. Etzion conjectured that the necessary conditions v 1 (mod 3) and v ; 7 are also sufficient for the existence of a GS(2,4,v,2). Except for the example of a GS(2,4,10,2) and some recursive constructions given by Etzion, nothing else is known about this conjecture. In this paper, Weil's theorem on character sum estimates is used to show that the conjecture is true for any prime power v 7 (mod 12) except v = 7, for which there does not exist a GS(2,4,7,2).     

Constant Weight Codes and Group Divisible Designs

The study of a class of optimal constant weight codes over arbitrary alphabets was initiated by Etzion, who showed that such codes are equivalent to special GDDs known as generalized Steiner systems GS(t,k,n,g) Etzion. This paper presents new constructions for these systems in the case t=2, k=3. In particular, these constructions imply that the obvious necessary conditions on the length n of the code for the existence of an optimal weight 3, distance 3 code over an alphabet of arbitrary size are asymptotically sufficient.     

Halving Steiner 2-designs

A Steiner 2-design S(2,k,v) is said to be halvable if the block set can be partitioned into two isomorphic sets. This is equivalent to an edge-disjoint decomposition of a self-complementary graph G on v vertices into K_ks. The obvious necessary condition of those orders v for which there exists a halvable S(2,k,v) is that v admits the existence of an S(2,k,v) with an even number of blocks. In this paper, we give an asymptotic solution for various block sizes. We prove that for any k?5 or any Mersenne prime k, there is a constant number v₀ such that if v>v₀ and v satisfies the above necessary condition, then there exists a halvable S(2,k,v). We also show that a halvable S(2,2ⁿ,v) exists for over a half of possible orders. Some recursive constructions generating infinitely many new halvable Steiner 2-designs are also presented.     

Generalized Steiner systems with block size three and group size g ≡ 3(mod 6)

Generalized Steiner Systems, GS(2, 3, n, g), are equivalent to maximum constant weight codes over an alphabet of size g + 1 with distance 3 and weight 3 in which each codeword has length n. We construct Generalized Steiner Triple Systems, GS(2, 3, n, g), when g ≡ 3(mod 6). © 1997 John Wiley & Sons, Inc. J Combin Designs 5:417–432, 1997     

Existence results for near resolvable designs

A near resolvable design, NRB(v, k), is a balanced incomplete block design whose block set can be partitioned into v classes such that each class contains every point of the design but one, and each point is missing from exactly one class. The necessary conditions for the existence of near resolvable designs are v ≡ 1 mod k and λ = k ? 1. These necessary conditions have been shown to be sufficient for k ? {2,3,4} and almost always sufficient for k ? {5,6}. We are able to show that there exists an integer n₀(k) so that NRB(v,k) exist for all v > n₀(k) and v ≡ 1 mod k. Using some new direct constructions we show that there are many k for which it is easy to compute an explicit bound on n₀(k). These direct constructions also allow us to build previously unknown NRB(v,5) and NRB(v,6). © 1995 John Wiley & Sons, Inc.     

Generalized steiner triple systems with group size five

Generalized Steiner triple systems, GS(2, 3, n, g) are used to construct maximum constant weight codes over an alphabet of size g+1 with distance 3 and weight 3 in which each codeword has length n. The existence of GS(2, 3, n, g) has been solved for g=2, 3, 4, 9. In this paper, by introducing a special kind of holey generalized Steiner triple systems (denoted by HGS(2, 3, (n, u), g)), singular indirect product (SIP) construction for GDDs is used to construct generalized Steiner systems. The numerical necessary conditions for the existence of a GS(2, 3, n, g) are shown to be sufficient for g=5.     

Linearizability of d-webs, d ≥ 4, on two-dimensional manifolds

We find d − 2 relative differential invariants for a d-web, d ≥ 4, on a two-dimensional manifold and prove that their vanishing is necessary and sufficient for a d-web to be linearizable. If one writes the above invariants in terms of web functions f(x, y) and g ₄(x, y),..., g _d (x, y), then necessary and sufficient conditions for the linearizabilty of a d-web are two PDEs of the fourth order with respect to f and g ₄, and d − 4 PDEs of the second order with respect to f and g ₄,..., g _d . For d = 4, this result confirms Blaschke’s conjecture on the nature of conditions for the linearizabilty of a 4-web. We also give the Mathematica codes for testing 4- and d-webs (d > 4) for linearizability and examples of their usage.     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

3-(v, 4, 1) covering designs with chromatic numbers 2 and 3

A t-(v, k, λ) covering design is a pair (X, B) where X is a v-set and B is a collection of k-sets in X, called blocks, such that every t element subset of X is contained in at least λ blocks of B. The covering number, C_λ(t, k, v), is the minimum number of blocks a t-(v, k, λ) covering design may have. The chromatic number of (X, B) is the smallest m for which there exists a map φ: X → Z_m such that ∣φ((β)∣ ≥2 for all β ∈ B, where φ(β) = {φ(x): x ∈ β}. The system (X, B) is equitably m-chromatic if there is a proper coloring φ with minimal m for which the numbers ∣φ^?1(c)∣ c ∈ Z_m differ from each other by at most 1. In this article we show that minimum, (i.e., ∣B∣ = C λ (t, k, v)) equitably 3-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0 (mod 6), v ≥ 18 for v ≥ 1, 13 (mod 36), v ≡ 13 and for all numbers v = n, n + 1, where n ≡ 4, 8, 10 (mod 12), n ≥ 16; and n = 6.5^a 13^b 17^c ?4, a + b + c > 0, and n = 14, 62. We also show that minimum, equitably 2-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0, 5, 9 (mod 12), v ≥ 0, v = 2.5^a 13^b 17^c + 1, a + b + c > 0, and v = 23. © 1993 John Wiley & Sons, Inc.     

Doubling and Tripling Constructions for Defining Sets in Steiner Triple Systems

 A minimal defining set of a Steiner triple system on v points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v+1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on 3 ⁿ points, we construct minimal defining sets of volumes varying by as much as 7 ⁿ⁻² . Received: September 16, 2000 Final version received: September 13, 2001 RID="*" ID="*" Research supported by the Australian Research Council A49937047, A49802044     

New type B colorable S(2, 4, v) designs

An S(2, 4, v) design has a type B χ‐coloring if it is possible to assign one of χ colors to each point such that each block contains three points of one color and one point of a different color, and all χ colors are used. In this article we describe the constructions of type B χ‐colorable S(2, 4, v)s for (v, χ) = (61, 3), (100, 2) and (109, 3), and we give a new general construction. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 357–368, 2007     

On Connected [g,f +1]-Factors in Graphs

Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z⁺-{1} such that g(v) ≤ f(v) ≤ d_G(v) for all v ∈V (G), where d_G(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs. * The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025. † The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org) and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204).     

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

Resolvable Mendelsohn designs with block size 4

Summary Letv andK be positive integers. A (v, k, 1)-Mendelsohn design (briefly (v, k, 1)-MD) is a pair (X,B) whereX is av-set (ofpoints) andB is a collection of cyclically orderedk-subsets ofX (calledblocks) such that every ordered pair of points ofX are consecutive in exactly one block ofB. A necessary condition for the existence of a (v, k, 1)-MD isv(v–1) 0 (modk). If the blocks of a (v, k, 1)-MD can be partitioned into parallel classes each containingv/k blocks wherev ) (modk) or (v – 1)/k blocks wherev 1 (modk), then the design is calledresolvable and denoted briefly by (v, k, 1)-RMD. It is known that a (v, 3,1)-RMD exists if and only ifv 0 or 1 (mod 3) andv 6. In this paper, it is shown that the necessary condition for the existence of a (v, 4, 1)-RMD, namelyv 0 or 1 (mod 4), is also sufficient, except forv = 4 and possibly exceptingv = 12. These constructions are equivalent to a resolvable decomposition of the complete symmetric directed graphK _v ^* onv vertices into 4-circuits.Research supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-5320.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected

An undirected graph G = (V, E) is called \mathbbZ₃{\mathbb{Z}_3}-connected if for all b: V ? \mathbbZ₃{b: V \rightarrow \mathbb{Z}_3} with ?_{v ? V}b(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a \mathbbZ₃{\mathbb{Z}_3}-valued nowhere-zero flow f: A? \mathbbZ₃-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?_{e ? d⁺(v)}f(e)-?_{e ? d^-(v)}f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are \mathbbZ₃{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the \mathbbZ₃{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs.