Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ⁻¹-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ⁻¹-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2⁻¹-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2⁻¹-isomorphic and 3⁻¹-isomorphic pairs of STS(15)s.     

A new existence proof for large sets of disjoint Steiner triple systems

A Steiner triple system of order v (briefly STS(v)) consists of a v-element set X and a collection of 3-element subsets of X, called blocks, such that every pair of distinct points in X is contained in a unique block. A large set of disjoint STS(v) (briefly LSTS(v)) is a partition of all 3-subsets (triples) of X into v-2 STS(v). In 1983–1984, Lu Jiaxi first proved that there exists an LSTS(v) for any v≡1 or with six possible exceptions and a definite exception v=7. In 1989, Teirlinck solved the existence of LSTS(v) for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems.     

Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ^?1-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ^?1-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2^?1-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2^?1-isomorphic and 3^?1-isomorphic pairs of STS(15)s.     

A small basis for four-line configurations in steiner triple systems. Dedicated to the memory of gemma holly griggs

Formulae for the numbers of two, three, and four-line configurations in a Steiner triple system of order v, STS(v), are given. While the formulae for two and three-line configurations depend only on v, the same is true for only 5 of the 16 four-line configurations. For the other 11 and fixed v, the number of occurrences of any one of them, in particular the Pasch configuration, determines the number of occurrences of all the others. © 1995 John Wiley & Sons, Inc.     

Some new perfect Steiner triple systems

In a Steiner triple system STS(v) = (V, B), for each pair {a, b} ⊂ V, the cycle graph G_a,b can be defined as follows. The vertices of G_a,b are V \ {a, b, c} where {a, b, c} ∈ B. {x, y} is an edge if either {a, x, y} or {b, x, y} ∈ B. The Steiner triple system is said to be perfect if the cycle graph of every pair is a single (v − 3)-cycle. Perfect STS(v) are known only for v = 7, 9, 25, and 33. We construct perfect STS (v) for v = 79, 139, 367, 811, 1531, 25771, 50923, 61339, and 69991. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 327–330, 1999     

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.     

An upper bound for domination number of 5-regular graphs

Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n.     

Pairwise “Orthogonal generalized room squares” and equidistant permutation arrays

A generalized Room square S(r, λ; v) is an r × r array such that every cell in the array contains a subset of a v-set V. This subset could of course be the empty set. The array has the property that every element of V is contained precisely once in every row and column and that any two distinct elements of V are contained in precisely λ common cells. In this paper we define pairwise orthogonal generalized Room squares and give a construction for these using finite projective geometries. This is another generalization of the concept of pairwise orthogonal latin squares. We use these orthogonal arrays to construct permutations having a constant Hamming distance.     

On the Intersection Problem for Steiner Triple Systems of Different Orders

A Steiner triple system of order v, or STS(v), is a pair (V, ) with V a set of v points and a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS(u), (U, ), and STS(v), (V, ), with U⊆V. The case where U=V was solved by Lindner and Rosa in 1975. Here, we let U⊂V and completely solve this question for v−u=2,4 and for v≥2u−3. supported by NSERC research grant #OGP0170220. supported by NSERC postdoctoral fellowship. supported by NSERC research grant #OGP007621.     

Characterizations of trees with equal domination parameters

Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set, if every vertex not in S is adjacent to a vertex in S and to a vertex in V − S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a restrained dominating set of G. A set S ⊆ V is a weak dominating set of G if, for every u in V − S, there exists a v ∈ S such that uv ∈ E and deg u ≥ deg v. The weak domination number of G, denoted by γ_w(G), is the minimum cardinality of a weak dominating set of G. In this article, we provide a constructive characterization of those trees with equal independent domination and restrained domination numbers. A constructive characterization of those trees with equal independent domination and weak domination numbers is also obtained. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 142–153, 2000     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

List Colorings of K5‐Minor‐Free Graphs With Special List Assignments

The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K₅‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[S_k], where S_k: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(S_k) in G between the components of G[S_k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012     

A construction for large sets of disjoint Kirkman triple systems

A Steiner system S(t, k, v) is called i-resolvable, 0 < i < t, if its block set can be partitioned into S(i, k, v). In this paper, a 2-resolvable S(3, 4, v) is used to construct a large set of disjoint Kirkman triple systems of order 3v − 3 (briefly LKTS) and some new orders for LKTS are then obtained. Research supported by Tianyuan Mathematics Foundation of NSFC Grant 10526032 and Natural Science Foundation of Universities of Jiangsu Province Grant 05KJB110111.     

Degree sequences of <Emphasis Type="Italic">k</Emphasis>-multi-hypertournaments

Let n and k（n ≥ k 〉 1） be two non-negative integers.A k-multi-hypertournament on n vertices is a pair（V,A）,where V is a set of vertices with ｜V｜=n,and A is a set of k-tuples of vertices,called arcs,such that for any k-subset S of V,A contains at least one（at most k!） of the k! k-tuples whose entries belong to S.The necessary and suffcient conditions for a non-decreasing sequence of non-negative integers to be the out-degree sequence（in-degree sequence） of some k-multi-hypertournament are given.     

Onc 0 sequences in Banach spaces

A Banach space has property (S) if every normalized weakly null sequence contains a subsequences equivalent to the unit vector basis ofc ₀. We show that the equivalence constant can be chosen “uniformly”, i.e., independent of the choice of the normalized weakly null sequence. Furthermore we show that a Banach space with property (S) has property (u). This solves in the negative the conjecture that a separable Banach space with property (u) not containingl ₁ has a separable dual. This is part of this author's Ph.D. dissertation prepared at The University of Texas at Austin under the supervision of H. P. Rosenthal.     

Resolvable minimum coverings with quadruples

Let V be a finite set of v elements. A covering of the pairs of V by k-subsets is a family F of k-subsets of V, called blocks, such that each pair in V occurs in at least one member of F. For fixed v and k, the covering problem is to determine the number of blocks in any minimum covering. A minimum covering is resolvable if we can partition the blocks into classes (called resolution classes) such that every element is contained in precisely one block of each class. A resolvable minimum covering of the pairs of V by k-subsets is denoted by RC(v, k). In this article, we show that there exist RC(v, 4) for v ≡ 0 (mod 4) except for v = 12 and possibly for v ∈ {104, 108, 116, 132, 156, 164, 204, 212, 228, 276}. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 431–450, 1998     

Ultracritical and hypercritical binary structures

A binary structure is an arc-coloured complete digraph, without loops, and with exactly two coloured arcs (u,v) and (v,u) between distinct vertices u and v. Graphs, digraphs and partial orders are all examples of binary structures. Let B be a binary structure. With each subset W of the vertex set V(B) of B we associate the binary substructure B[W] of B induced by W. A subset C of V(B) is a clan of B if for any c,d∈C and v∈V(B)?C, the arcs (c,v) and (d,v) share the same colour and similarly for (v,c) and (v,d). For instance, the vertex set V(B), the empty set and any singleton subset of V(B) are clans of B. They are called the trivial clans of B. A binary structure is primitive if all its clans are trivial.With a primitive and infinite binary structure B we associate a criticality digraph (in the sense of [11]) defined on V(B) as follows. Given v≠w∈V(B), (v,w) is an arc of the criticality digraph of B if v belongs to a non-trivial clan of B[V(B)?{w}]. A primitive and infinite binary structure B is finitely critical if B[V(B)?F] is not primitive for each finite and non-empty subset F of V(B). A finitely critical binary structure B is hypercritical if for every v∈V(B), B[V(B)?{v}] admits a non-trivial clan C such that |V(B)?C|≥3 which contains every non-trivial clan of B[V(B)?{v}]. A hypercritical binary structure is ultracritical whenever its criticality digraph is connected.The ultracritical binary structures are studied from their criticality digraphs. Then a characterization of the non-ultracritical but hypercritical binary structures is obtained, using the generalized quotient construction originally introduced in [1].     

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     

Representing Graphs in Steiner Triple Systems

Let G =  (V, E) be a simple graph and let T =  (P, B) be a Steiner triple system. Let φ be a one-to-one function from V to P. Any edge e =  {u, v} has its image {φ(u), φ(v)} in a unique block in B. We also denote this induced function from edges to blocks by φ. We say that T represents G if there exists a one-to-one function φ : V → P such that the induced function φ : E → B is also one-to-one; that is, if we can represent vertices of the graph by points of the triple system such that no two edges are represented by the same block. In this paper we examine when a graph can be represented by an STS. First, we find a bound which ensures that every graph of order n is represented in some STS of order f(n). Second, we find a bound which ensures that every graph of order n is represented in every STS of order g(n). Both of these answers are related to finding an independent set in an STS. Our question is a generalization of finding such independent sets. We next examine which graphs can be represented in STS’s of small orders. Finally, we give bounds on the orders of STS’s that are guaranteed to embed all graphs of a given maximum degree.