Switching for 2-designs

Designs, Codes and Cryptography - In this paper, we introduce a switching for 2-designs, which defines a type of trade. We illustrate this method by applying it to some symmetric...     

Extended (2, 4)-designs

In this paper, the concept of an extended (2, 4)-design is introduced. An extended (2, 4)-design is a pair (X, $\text{B}$) where X is a finite set and $\text{B}$ is a collection of 4-tuples of not necessarily distinct elements of X, such that every pair of not necessarily distinct elements of X is contained in exactly one member of $\text{B}$. It is shown that an extended (2,4)-design of order n exists for every positive integer n except n = 6, 8 and 9. Several inequivalent designs of order n are obtained.     

Quasi-symmetric 2, 3, 4-designs

Quasi-symmetric designs are block designs with two block intersection numbersx andy It is shown that with the exception of (x, y)=(0, 1), for a fixed value of the block sizek, there are finitely many such designs. Some finiteness results on block graphs are derived. For a quasi-symmetric 3-design with positivex andy, the intersection numbers are shown to be roots of a quadratic whose coefficients are polynomial functions ofv, k and λ. Using this quadratic, various characterizations of the Witt—Lüneburg design on 23 points are obtained. It is shown that ifx=1, then a fixed value of λ determines at most finitely many such designs.     

Schematic 4-designs

We study 4-designs with three intersection numbers. By the Cameron-Delsarte theorem, the blocks form a symmetric three-class association scheme. This imposes strong restrictions on the parameters of such designs. We calculate the eigenvalues of the association scheme from the design parameters and determine all admissible parameters with at most 1000 points. An infinite family of admissible parameters is discovered. Designs with small admissible parameters exist and are related to the quadratic residue codes.     

色数等于选择数的4-正则图

设Hn(n≥5)表示一个图:以1,2,．．．,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n．这篇文章证明了,Hn的色数等于它的选择数．结果被用于刻画最大度至多2的图的列表全色数．     

On 2-designs

Denote by M_v the set of integers b for which there exists a 2-design (linear space) with v points and b lines. M_v is determined as accurately as possible. On one hand, it is shown for v > v₀ that M_v contains the interval [v + p + 1, v + p + q ? 1]. On the other hand for v of the form p² + p + 1 it is shown that the interval [v + 1, v + p ? 1] is disjoint from M_v; and if v > v₀ and p is of the form q² + q, then an additional interval [v + p + 1, v + p + q ? 1] is disjoint from M_v.     

Miscellaneous classification results for 2-designs

An orderly algorithm combined with clique searching is used to show that there are—up to isomorphism, in all cases—325,062 resolvable 2-(16,4,2) designs with 339,592 resolutions, 19,072,802 2-(13,6,5) designs, and 15,111,019 2-(14,7,6) designs. Properties of the classified designs are further discussed.     

Non-symmetric 2-designs modulo 2

Necessary conditions are obtained for the existence of a 2 – (v, k, ) design, for which the block intersection sizess ₁,s ₂, ...,s _n satisfys ₁ s ₂ ... s _n s (mod 2 ^e ), wheree is odd. These conditions are obtained by combining restrictions on the Smith Normal Form of the incidence matrix of the design with some well known properties of self-orthogonal binary codes with all weights divisible by 4.Research done at AT&T Bell Laboratories.     

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.     

A new family of 4-designs

We construct a family of simple 4-designs with parameters 4 – (2 ^f + 1, 6, 10),f odd.     

Real 2-Regular Classes and 2-Blocks

Suppose that G is a finite group. We show that every 2-block of G has a defect class which is real. As a partial converse, we show that if G has a real 2-regular class with defect group D and if N(D)/D has no dihedral subgroup of order 8, then G has a real 2-block with defect group D. More generally, we show that every 2-block of G which is weakly regular relative to some normal subgroup N has a defect class which is real and contained in N. We give several applications of these results and also investigate some consequences of the existence of non-real 2-blocks.     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

4-Regular Vertex-Transitive Tilings of E 3

{There exist precisely 149 topological types of semipolytopal tile-transitive tilings of E ³ by ``extetrahedra' (obtained from tetrahedra by introducing certain new vertices of degree 2 ). Dualization gives rise to 149 types of 4-regular vertex-transitive tilings. The 4-coordinated networks carried by these tilings are closely related to crystal structures such as zeolites or diamond. These results are obtained using ``combinatorial tiling theory.'} Received February 12, 1999, and in revised form September 21, 1999. Online publication May 15, 2000.     

Parameterized Algorithms in Smooth 4-Regular Hamiltonian Graphs

Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this paper we show that these problems are fixed parameter tractable if we choose the number of inner cycles as parameter. The reseach has been supported by International Science Programme (ISP) of Sweden, under the project titled “The Eastern African Universities Mathematics Programme (EAUMP)”.