Further Results on the Existence of Splitting BIBDs and Application to Authentication Codes

Let (v,u×c,λ)-splitting BIBD denote a (v,u×c,λ)-splitting balanced incomplete block design of order v with block size u×c and index λ. Necessary conditions for the existence of a (v,u×c,λ)-splitting BIBD are v≥uc, λ(v−1)≡0 (mod c(u−1)) and λ v(v−1)≡0 (mod (c ² u(u−1))). We show in this paper that the necessary conditions for the existence of a (v,3×3,λ)-splitting BIBD are also sufficient with possible exceptions when (1) (v,λ)∈{(55,1),(39,9k):k=1,2,…}, (2) λ≡0 (mod 54) and v≡0 (mod 2). We also show that there exists a (v,3×4,1)-splitting BIBD when v≡1 (mod 96). As its application, we obtain a new infinite class of optimal 4-splitting authentication codes.     

The Existence of (ν,6, λ)-Perfect Mendelsohn Designs with λ > 1

The basic necessary conditions for the existence of a (v, k, λ)-perfect Mendelsohn design (briefly (v, k, λ)-PMD) are v ≥ k and λ v(v − 1) ≡ 0 (mod k). These conditions are known to be sufficient in most cases, but certainly not in all. For k = 3, 4, 5, 7, very extensive investigations of (v, k, λ)-PMDs have resulted in some fairly conclusive results. However, for k = 6 the results have been far from conclusive, especially for the case of λ = 1, which was given some attention in papers by Miao and Zhu [34], and subsequently by Abel et al. [1]. Here we investigate the situation for k = 6 and λ > 1. We find that the necessary conditions, namely v ≥ 6 and λ v(v − 1)≡0 (mod 6) are sufficient except for the known impossible cases v = 6 and either λ = 2 or λ odd. Researcher F.E. Bennett supported by NSERC Grant OGP 0005320.     

The Spectrum of Tetrahedral Quadruple Systems

An ordered analogue of quadruple systems is tetrahedral quadruple systems. A tetrahedral quadruple system of order v and index λ, TQS(v, λ), is a pair (S, T){(S, \mathcal{T})} where S is a finite set of v elements and T{\mathcal{T}} is a family of oriented tetrahedrons of elements of S called blocks, such that every directed 3-cycle on S is contained in exactly λ blocks of T{\mathcal{T}} . When λ = 1, the spectrum problem of TQS(v, 1) has been completely determined. It is proved that a TQS(v, λ) exists if and only if λ(v − 1)(v − 2) ≡ 0 (mod 3), λv(v − 1)(v − 2) ≡ 0 (mod 4) and v ≥ 4.     

On the existence of nearly Kirkman triple systems with subsystems

It is proved in this paper that the necessary and sufficient conditions for the existence of an incomplete nearly Kirkman triple system INKTS(u, v) are u ≡ v ≡ 0 (mod 6), u ≥ 3v. As a consequence, we obtain a complete solution to the embedding problem for nearly Kirkman triple systems.      

On the embeddings of mendelsohn triple systems

It is proved in this paper that there exists an incomplete Mendelsohn triple system IMTS(u,v; λ) if and only ifλ(u-v)(u-2v-1)≡0(mod 3),u≥2v+1 and (u, v, λ) ≠ (6, 1, 1). As a consequence, it is proved that for any given λ≥1, a Mendelsohn triple system MTS (v, λ) can be embedded in an MTS (u, λ) if and only ifλu(u-1)≡0(mod 3) andu≥2v+1. Project supported by the National Natural Science Foundation of China.     

The Existence of BIB Designs

Abstract Given any positive integers k≥ 3 and λ, let c(k, λ) denote the smallest integer such that v∈B(k, λ) for every integer v≥c(k, λ) that satisfies the congruences λv(v− 1) ≡ 0(mod k(k− 1)) and λ(v− 1) ≡ 0(mod k− 1). In this article we make an improvement on the bound of c(k, λ) provided by Chang in [4] and prove that . In particular, . Supported by NSFC Grant No. 19701002 and Huo Yingdong Foundation     

Incomplete group divisible designs with block size four and general index

In this paper, we investigate the existence of incomplete group divisible designs (IGDDs) with block size four, group-type (g, h) u and general index λ. The necessary conditions for the existence of such a design are that u ≥ 4, g ≥ 3h, λg(u 1) ≡ 0 (mod 3), λ(g h)(u 1) ≡ 0 (mod 3), and λu(u 1)(g 2 h 2 ) ≡ 0 (mod 12). These necessary conditions are shown to be sufficient for all λ≥ 2. The known existence result for λ = 1 is also improved.     

Reduction for primitive flag-transitive (<Emphasis Type="Italic">v</Emphasis>, <Emphasis Type="Italic">k</Emphasis>, 4)-symmetric designs

It has been shown that if a (v, k, λ)-symmetric design with λ ≤ 3 admits a flag-transitive automorphism group G which acts primitively on points, then G must be of affine or almost simple type. Here we extend the result to λ = 4.     

P 3-factorization of complete multipartite graphs

In this note it is shown that a necessary and sufficient condition for the existence of a P3-factorizatlon of complete multipartite graph λK, is (1) m≥3, (2) mn≡0(mod 3) and (3)λ(m-1)n≡0(mod 4).     

-Decompositions of and D v ∪P where P is a 2-Regular Subgraph of D v

In this paper, we extend the study of C₄-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D_v, then and D_v∪P can be decomposed into directed 4-cycles, respectively, if and only if v(v−1)−|E(P)|≡0(mod 4) and v(v−1)+|E(P)|≡0(mod 4) where |E(P)| denotes the number of directed edges of P, and v≥8.     

Large sets of pure directed triple systems with index λ

A directed triple system of order v with index λ, briefly by DTS（v,λ）, is a pair （X, B） where X is a v-set and B is a collection of transitive triples （blocks） on X such that every ordered pair of X belongs to λ blocks of B. A simple DTS（v, λ） is a DTS（v, λ） without repeated blocks. A simple DTS（v, ）,） is called pure and denoted by PDTS（v, λ） if （x, y, z） ∈ B implies （z, y, x）, （z, x, y）, （y, x, z）, （y, z, x）, （x, z, y） B. A large set of disjoint PDTS（v, λ）, denoted by LPDTS（v, λ）, is a collection of 3（v - 2）/λ disjoint pure directed triple systems on X. In this paper, some results about the existence for LPDTS（v, λ） are presented. Especially, we determine the spectrum of LPDTS（v, 2）.     

The spectrum of path factorization of bipartite multigraphs

LetλK_(m,n)be a bipartite multigraph with two partite sets having m and n vertices, respectively.A P_v-factorization ofλK_(m,n)is a set of edge-disjoint P_v-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).When v is an even number,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P_v-factorization ofλK_(m,n).When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P_(4k 1)-factorization ofλK_(m,n)are(1)2km≤(2k 1)n,(2)2kn≤(2k 1)m,(3)m n≡0(mod 4k 1),(4)λ(4k 1)mn/[4k(m n)]is an integer.     

On the multiplier conjecture

The Multiplier Theorem is a celebrated theorem in the Design theory. The conditionp>λ is crucial to all known proofs of the multiplier theorem. However in all known examples of difference sets μ _p . is a multiplier for every primep with (p, v)=1 andp‖n. Thus there is the multiplier conjecture: “The multiplier theorem holds without the assumption thatp>λ”. The general form of the multiplier theorem may be viewed as an attempt to partially resolve the multiplier conjecture, where the assumption “p>λ” is replaced by “n ₁>λ”. Since then Newman (1963), Turyn (1964), and McFarland (1970) attempted to partially resolve the multiplier conjecture (see [7], [8], [9]). This paper will prove the following result using the representation theory of finite groups and the algebraic number theory: LetG be an abelian group of orderv,v ₀ be the exponent ofG, andD be a (v, k, λ)-difference set inG. Ifn=2_{n 1}, then the general form of the multiplier theorem holds without the assumption thatn ₁>λ in any of the following cases:

The spectrum of (<Emphasis Type="Italic">gv</Emphasis>, <Emphasis Type="Italic">g</Emphasis>, 3, λ)-DF in <Emphasis Type="Italic">Z</Emphasis><Subscript><Emphasis Type="Italic">gv</Emphasis></Subscript>

In this paper, the necessary and sufficient conditions for the existence of a (gv, g, 3, λ)-difference family in Z _gv are established. As a consequence, the existence spectrum of a cyclic (3, λ)-GDD of type g ^v without short orbits is determined. This work was supported by National Natural Science Foundation of China (Grants Nos. 10771013, 10831002)     

有向Kirkman填充设计的谱

§ 1　IntroductionLet X be a set of v points.A packing(directed packing) of X is a collection of subsets(ordered subsets) of X(called blocks) such that any pair(ordered pair) of distinct pointsfrom X occur together in atmostone block in the collection.A packing(directed packing)is called resolvable ifitsblock setadmitsa partition into parallel classes,each parallel classbeing a partition of the pointset X.A Kirkman triple system KTS(v) is a collection Tof3 -subsets of X(triples) suchthat …     

P4k?1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P _v-factorization of λK _m,n is a set of edge-disjoint P _v -factors of λK _m,n which partition the set of edges of λK _m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k − 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P _4k−1-factorization of λK _m,n is (1) (2k − 1)m ⩽ 2kn, (2) (2k − 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k − 1), (4) λ(4k − 1)mn/[2(2k − 1)(m + n)] is an integer.     

A new class of splitting 3-designs

Splitting t-designs were first formulated by Huber in recent investigation of optimal (t − 1)-fold secure splitting authentication codes. In this paper, we investigate the construction and existence of splitting t-designs t-(v, u × k, 1) splitting designs and, show that there exists a 3-(v, 3 × 2, 1) splitting design if and only if v ≡ 2 (mod 8). As its application, we obtain a new infinite class of optimal 2-fold secure splitting authentication codes.     

Some progress on the existence of 1-rotational Steiner triple systems

A Steiner triple system of order v (briefly STS(v)) is 1-rotational under G if it admits G as an automorphism group acting sharply transitively on all but one point. The spectrum of values of v for which there exists a 1-rotational STS(v) under a cyclic, an abelian, or a dicyclic group, has been established in Phelps and Rosa (Discrete Math 33:57–66, 1981), Buratti (J Combin Des 9:215–226, 2001) and Mishima (Discrete Math 308:2617–2619, 2008), respectively. Nevertheless, the spectrum of values of v for which there exists a 1-rotational STS(v) under an arbitrary group has not been completely determined yet. This paper is a considerable step forward to the solution of this problem. In fact, we leave as uncertain cases only those for which we have v =  (p ³−p)n +  1 ≡ 1 (mod 96) with p a prime, n \not o 0{n \not\equiv 0} (mod 4), and the odd part of (p ³ − p)n that is square-free and without prime factors congruent to 1 (mod 6).     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].