Search

In this paper, we are interested in the following question: given an arbitrary Steiner triple system S on m vertices and any 3‐uniform hypertree T on n vertices, is it necessary that S contains T as a subgraph provided m≥(1+μ)n? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive. [ABSTRACT FROM AUTHOR]

An H(m,g,k,3) design is a triple (X,T,B), where X is a set of mg points, T a partition of X into m disjoint sets of size g, and B a set of k‐element transverses of T, such that each 3‐element transverse of T is contained in exactly one of them. In 1990, Mills determined the existence of an H(m,g,4,3) design with m≠5. In this paper, an efficient construction shows that an H(5,g,4,3) exists for any integer g≡2,10(mod12) with g≥10. Consequently, the necessary and sufficient conditions for the existence of an H(m,g,4,3) design are m≥4, mg≡0(mod2), and g(m−1)(m−2)(mod3), with a definite exception (m,g)=(5,2). [ABSTRACT FROM AUTHOR]

An Euler tour of a hypergraph (also called a rank-2 universal cycle or 1-overlap cycle in the context of designs) is a closed walk that traverses every edge exactly once. In this paper, using a graph-theoretic approach, we prove that every triple system with at least two triples is eulerian, that is, it admits an Euler tour. Horan and Hurlbert have previously shown that for every admissible order >3, there exists a Steiner triple system with an Euler tour, while Dewar and Stevens have proved that every cyclic Steiner triple system of order >3 and every cyclic twofold triple system admits an Euler tour. [ABSTRACT FROM AUTHOR]

A dihedral SQS is an SQS admitting a point-regular dihedral automorphism group. Some constructions of dihedral SQSs are established in this paper. We also prove that for v ≡ 2 , 4 ( m o d 6 ) , there is a dihedral SQS ( v ) if there is a dihedral H ( p , 2 , 4 , 3 ) design or an S -cyclic SQS ( 2 p ) for each odd prime divisor p of v . As a corollary, we enlarge the set of known values of v for which there exists a dihedral SQS ( v ) . [ABSTRACT FROM AUTHOR]

Given a 2 - ( v , k , λ ) design, S = ( X , B ) , a zero-sum n -flow of S is a map f : B ⟶ { ± 1 , … , ± ( n − 1 ) } such that for any point x ∈ X , the sum of f over all the blocks incident with x is zero. It has been conjectured that every Steiner triple system, STS ( v ) , on v points ( v > 7 ) admits a zero-sum 3 -flow. We show that for every pair ( v , λ ) for which a triple system, TS ( v , λ ) , exists, there exists one which has a zero-sum 3 -flow, except when ( v , λ ) ∈ { ( 3 , 1 ) , ( 4 , 2 ) , ( 6 , 2 ) , ( 7 , 1 ) } . We also give a O ( λ 2 v 2 ) bound on n and a recursive result which shows that every STS ( v ) with a zero-sum 3 -flow can be embedded in an STS ( 2 v + 1 ) with a zero-sum 3 -flow if v ≡ 3 ( m o d 4 ) , a zero-sum 4 -flow if v ≡ 3 ( m o d 6 ) and with a zero-sum 5 -flow if v ≡ 1 ( m o d 4 ) . [ABSTRACT FROM AUTHOR]

We introduce a class of non-Moufang loops satisfying Moufang's theorem. [ABSTRACT FROM AUTHOR]

In this paper, we obtain the comparison results for solutions of a class of sublinear elliptic equations using Steiner symmetrization. [ABSTRACT FROM PUBLISHER]

Abstract: A flower in a Steiner system is the set of all blocks containing a given point. The flower intersection problem for Steiner systems is the determination of all pairs such that there exists a pair of Steiner systems and of order having a common flower satisfying . In this paper the flower intersection problem for a pair of ’s is investigated. Let a pair of ’s intersecting in blocks, of them being the blocks of a common flower . Let , where and is the number of blocks of an . It is established that for any positive integer and . [Copyright &y& Elsevier]

Abstract: Franek et al. recently described four constructions for large sets of -intersecting Steiner triple systems of order (STS ) [F. Franek, M.J. Grannell, T.S. Griggs, A. Rosa, On the large sets of -intersecting Steiner triple systems of order , Des. Codes Cryptogr. 26 (2002) 243–256]. In this study we focus on large sets of -intersecting STS . Some recursive constructions are presented that involve three-wise balanced designs. By applying these constructions we obtain some new infinite classes of such large sets, and the large sets of -intersecting KTS are used to produce some new large sets of Kirkman triple systems. [Copyright &y& Elsevier]

Abstract: A flower, , around a point in a Steiner triple system is the set of all triples in which contain the point , namely . This paper determines the possible number of common flowers that two Steiner triple systems can have in common. For all admissible pairs where we construct a pair of Steiner triple systems of order where the flowers around elements of are identical in both Steiner triple systems, except for the pairs , and . Equivalently this result shows that there is a Steiner triple trade of foundation that can be embedded in a for each admissible and except when or . [Copyright &y& Elsevier]

Abstract: We study group gradings on Lie triple systems. In particular, the fine group gradings on simple Lie triple systems over an algebraically closed field whose standard embedding -graded Lie algebra is () or () are given. [Copyright &y& Elsevier]

Abstract: A Steiner quadruple system is said to be -resolvable if its blocks can be partitioned into parts such that each point of occurs in exactly two blocks in each part. The necessary condition for the existence of -resolvable Steiner quadruple systems s is or 10 (mod 12). Hartman and Phelps in [A. Hartman, K.T. Phelps, Steiner quadruple systems, in: J.H. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory, Wiley, New York, 1992, pp. 205–240] posed a question whether the necessary condition for the existence of -resolvable Steiner quadruple systems is sufficient. In this paper, we consider the last twenty orders of -resolvable Steiner quadruple systems and show that the necessary condition for the existence of -resolvable Steiner quadruple systems is also sufficient except for the order 10. [Copyright &y& Elsevier]

A family ( X, B), ( X, B), ..., ( X, B) of q STS( υ)s is a λ-fold large set of STS( υ) and denoted by LSTS( υ) if every 3-subset of X is contained in exactly λ STS( υ)s of the collection. It is indecomposable and denoted by IDLSTS( υ) if there does not exist an LSTS( υ) contained in the collection for any λ′ < λ. In this paper, we show that for λ = 5, 6, there is an IDLSTS( υ) for υ ≡ 1 or 3 (mod 6) with the exception IDLSTS(7). [ABSTRACT FROM AUTHOR]

Abstract: The block graph of a Steiner triple system of order v is a strongly regular graph. For large v, every strongly regular graph with these parameters is the block graph of a Steiner triple system, but exceptions exist for small orders. An explanation for some of the exceptional graphs is here provided via the concept of switching. (Group divisible designs corresponding to) Latin squares are also treated in an analogous way. Many new strongly regular graphs are obtained by switching and by constructing graphs with prescribed automorphisms. In particular, new strongly regular graphs with the following parameters that do not come from Steiner triple systems or Latin squares are found: , , , , , and . [Copyright &y& Elsevier]

Abstract: -resolvable candelabra quadruple systems play an important role in the construction of -resolvable Steiner quadruple systems. In this paper, we consider -resolvable candelabra quadruple systems with three groups and show that the necessary conditions on the existence of -RCQS when is even are also sufficient. As its application, we improve the existing result on -resolvable Steiner quadruple systems. [Copyright &y& Elsevier]

Abstract: A friendship 3-hypergraph is a 3-hypergraph in which for any 3 distinct vertices , and , there exists a unique fourth vertex such that , , are 3-hyperedges. Sós constructed friendship 3-hypergraphs using Steiner triple systems. Hartke and Vandenbussche showed that any friendship 3-hypergraph can be partitioned into ’s. (A is the set of four hyperedges of size three that can be formed from a set of 4 elements.) These ’s form a set of 4-tuples which we call a friendship design. We define a geometric friendship design to be a resolvable friendship design that can be embedded into an affine geometry. Refining the problem from friendship designs to geometric friendship designs allows us to state some structure results about these geometric friendship designs and decrease the search space when searching for geometric friendship designs. Hartke and Vandenbussche discovered 5 new examples of friendship designs which happen to be geometric friendship designs. We show the 3 non-isomorphic geometric designs on 16 vertices are the only such non-isomorphic geometric designs on 16 vertices. We also improve the known lower and upper bounds on the number of hyperedges in any friendship 3-hypergraph. Finally, we show that no friendship 3-hypergraph exists on 11 or 12 points. [Copyright &y& Elsevier]

We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An element means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is APX-hard when there are only three terminal nodes, thus answering an open question. Our main focus is on the special case when the graph is planar. We show that the problem of finding two element-disjoint Steiner trees in a planar graph is NP-hard. Similarly, the problem of finding two edge-disjoint Steiner trees in a planar graph is NP-hard. We design an algorithm for planar graphs that achieves an approximation guarantee close to 2. In fact, given a planar graph that is k element-connected on the terminals ( k is an upper bound on the number of element-disjoint Steiner trees), the algorithm returns $\lfloor\frac{k}{2} \rfloor-1$ element-disjoint Steiner trees. Using this algorithm, we get an approximation algorithm for the edge-disjoint version of the problem on planar graphs that improves on the previous approximation guarantees. We also show that the natural LP relaxation of the planar problem has an integrality ratio approaching 2. [ABSTRACT FROM AUTHOR]

Abstract: It is well known that, given a Steiner triple system, a quasigroup can be formed by defining an operation by the identities and , where is the third point in the block containing the pair . The same is true for a Mendelsohn triple system, where the pair is considered to be ordered. But it is not true in general for directed triple systems. However, directed triple systems which form quasigroups under this operation do exist. We call these Latin directed triple systems, and in this paper we begin the study of their existence and properties. [Copyright &y& Elsevier]

Abstract: It has been conjectured that any partial triple system of order u and index λ can be embedded in a triple system of order v and index λ whenever , is even and . This conjecture is known to hold for and for all even . Here the conjecture is proven for all remaining values of λ when . [Copyright &y& Elsevier]

Abstract: A two-fold pentagon system is a decomposition of the complete 2-multigraph (every two distinct vertices joined by two edges) into pentagons. A two-fold Steiner pentagon system is a two-fold pentagon system such that every pair of distinct vertices is joined by a path of length two in exactly two pentagons of the system. We consider two-fold Steiner pentagon systems with an additional property : for any two vertices, the two paths of length two joining them are distinct. We determine completely the spectrum for such systems, and point out an application of such systems to certain 4-cycle systems. [Copyright &y& Elsevier]

Abstract: A Steiner triple system of order , STS(), may be called equivalent to another STS() if one can be converted to the other by a sequence of three simple operations involving Pasch trades with a single negative block. It is conjectured that any two STS()s on the same base set are equivalent in this sense. We prove that the equivalence class containing a given system on a base set contains all the systems that can be obtained from by any sequence of well over one hundred distinct trades, and that this equivalence class contains all isomorphic copies of on . We also show that there are trades which cannot be effected by means of Pasch trades with a single negative block. [Copyright &y& Elsevier]

Abstract: Masbaum and Vaintrobʼs “Pfaffian matrix-tree theorem” implies that counting spanning trees of a 3-uniform hypergraph (abbreviated to 3-graph) can be done in polynomial time for a class of “3-Pfaffian” 3-graphs, comparable to and related to the class of Pfaffian graphs. We prove a complexity result for recognizing a 3-Pfaffian 3-graph and describe two large classes of 3-Pfaffian 3-graphs – one of these is given by a forbidden subgraph characterization analogous to Littleʼs for bipartite Pfaffian graphs, and the other consists of a class of partial Steiner triple systems for which the property of being 3-Pfaffian can be reduced to the property of an associated graph being Pfaffian. We exhibit an infinite set of partial Steiner triple systems that are not 3-Pfaffian, none of which can be reduced to any other by deletion or contraction of triples. We also find some necessary or sufficient conditions for the existence of a spanning tree of a 3-graph (much more succinct than can be obtained by the currently fastest polynomial-time algorithm of Gabow and Stallmann for finding a spanning tree) and a superexponential lower bound on the number of spanning trees of a Steiner triple system. [Copyright &y& Elsevier]

We consider the existence problem for 'Steiner networks' (trivalent graphs with 2 π/3 angles at each junction) in strictly convex domains, with 'Neumann' boundary conditions. For each of the three possible combinatorial possibilities, sufficient conditions on the domain are derived for existence. In addition, in each case explicit examples of nonexistence are given. [ABSTRACT FROM AUTHOR]

Abstract: We give a construction of a 2- design starting from a Steiner system and an affine plane of order n. This construction is applied to known classes of Steiner systems arising from affine and projective geometries, Denniston designs, and unitals. We also consider the extendability of these designs to 3-designs. [ABSTRACT FROM AUTHOR]

In this paper, the decompositions of quadratic Lie triple systems are discussed. Moreover the decomposition theorems of a quadratic Lie triple system into nondegenerate irreducible ideals are established. [ABSTRACT FROM AUTHOR]

Abstract: The (Euclidean) Vehicle Routing Allocation Problem (VRAP) is a generalization of Euclidean TSP. We do not require that all points lie on the salesman tour. However, points that do not lie on the tour are allocated, i.e., they are directly connected to the nearest tour point, paying a higher (per-unit) cost. More formally, the input is a set of n points and functions and . We wish to compute a subset and a salesman tour π through T such that the total length of the tour plus the total allocation cost is minimum. The allocation cost for a single point is , where is the nearest point on the tour. We give a PTAS with complexity for this problem. Moreover, we propose an -time PTAS for the Steiner variant of this problem. This dramatically improves a recent result of Armon et al. [A. Armon, A. Avidor, O. Schwartz, Cooperative TSP, in: Proceedings of the 14th Annual European Symposium on Algorithms, 2006, pp. 40–51]. [Copyright &y& Elsevier]

Abstract: Motivated by constructing cyclic simple designs, we consider how to decomposing all the triples of into cyclic triple systems. Furthermore, we define a large set of cyclic triple systems to be a decomposition of triples of into indecomposable cyclic designs. Constructions of decompositions and large sets are given. Some infinite classes of decompositions and large sets are obtained. Large sets of small with odd are also given. As an application, the results are used to construct cyclic simple triple systems. [Copyright &y& Elsevier]

Abstract: This paper takes a significant step towards confirming a long-standing and far-reaching conjecture of Peter J. Cameron and Cheryl E. Praeger. They conjectured in 1993 that there are no non-trivial block-transitive 6-designs. We prove that the Cameron–Praeger conjecture is true for the important case of non-trivial Steiner 6-designs, i.e. for 6- designs with , except possibly when the group is with or 3, and e is an odd prime power. [Copyright &y& Elsevier]

Abstract  A transformation of Steiner quadruple systems S(υ, 4, 3) is introduced. For a given system, it allows to construct new systems of the same order, which can be nonisomorphic to the given one. The structure of Steiner systems S(υ, 4, 3) is considered. There are two different types of such systems, namely, induced and singular systems. Induced systems of 2-rank r can be constructed by the introduced transformation of Steiner systems of 2-rank r − 1 or less. A sufficient condition for a Steiner system S(υ, 4, 3) to be induced is obtained. [ABSTRACT FROM AUTHOR]

Abstract: Generalized Steiner systems were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size with minimum Hamming distance , in which each codeword has length and weight . As to the existence of a , a lot of work has been done for , while not so much is known for . The notion GDD was first introduced by Chen et al. and used to construct . The necessary condition for the existence of a is . In this paper, it is proved that there exists a for any prime power and . By using this result, the known results on the existence of optimal quaternary constant weight codes are then extended. [Copyright &y& Elsevier]

Abstract: A -coloring of a graph by colors is a proper -coloring of such that in each color class there exists a vertex having neighbors in all the other color classes. The -chromatic number of a graph , denoted by , is the maximum for which has a -coloring by colors. It is obvious that . A graph is -continuous if for every between and there is a -coloring of by colors. In this paper, we study the -coloring of Kneser graphs and determine for some values of and . Moreover, we prove that is -continuous for . [Copyright &y& Elsevier]

Abstract: The concept of good large set of Steiner triple systems (or GLS in short) was introduced by Lu in his paper “on large sets of disjoint Steiner triple systems”, [J. Lu, On large sets of disjoint Steiner triple systems, I–III, J. Combin. Theory (A) 34 (1983) 140-182]. In this paper a doubling construction for GLSs is displayed and some existence results are obtained. [Copyright &y& Elsevier]

Abstract: An overlarge set of , denoted by , is a collection , where is a -set, each is a and forms a partition of all triples on . In this paper, we give a tripling construction for overlarge sets of . Our main result is that: If there exists an with a special property, then there exists an . It is obtained that there exists an for or , where prime power (mod 12) and . [Copyright &y& Elsevier]

Abstract: A Steiner triple system (briefly ST) is in 1–1 correspondence with a Steiner quasigroup or squag (briefly SQ) [B. Ganter, H. Werner, Co-ordinatizing Steiner systems, Ann. Discrete Math. 7 (1980) 3–24; C.C. Lindner, A. Rosa, Steiner quadruple systems: A survey, Discrete Math. 21 (1979) 147–181]. It is well known that for each or 3 (mod 6) there is a planar squag of cardinality [J. Doyen, Sur la structure de certains systems triples de Steiner, Math. Z. 111 (1969) 289–300]. Quackenbush expected that there should also be semi-planar squags [R.W. Quackenbush, Varieties of Steiner loops and Steiner quasigroups, Canad. J. Math. 28 (1976) 1187–1198]. A simple squag is semi-planar if every triangle either generates the whole squag or the 9-element squag. The first author has constructed a semi-planar squag of cardinality for all and or 3 (mod 6) [M.H. Armanious, Semi-planar Steiner quasigroups of cardinality 3, Australas. J. Combin. 27 (2003) 13–27]. In fact, this construction supplies us with semi-planar squags having only nontrivial subsquags of cardinality 9. Our aim in this article is to give a recursive construction as for semi-planar squags. This construction permits us to construct semi-planar squags having nontrivial subsquags of cardinality >9. Consequently, we may say that there are semi-planar (or semi-planar ) for each positive integer and each or 3 (mod 6) with having only medial subsquags at most of cardinality (sub-) for each . [Copyright &y& Elsevier]

Abstract: A hexagon triple is the graph consisting of the three triangles (triples) , and , where , and are distinct. The triple is called an inside triple. A hexagon triple system of order is a pair where is a collection of edge disjoint hexagon triples which partitions the edge set of with vertex set . The inside triples form a partial Steiner triple system. We show that any Steiner triple system of order can be embedded in the inside triples of a hexagon triple system of order approximately . [Copyright &y& Elsevier]

Abstract: Let be a directed/undirected graph, let , and let be an intersecting family on (that is, for any intersecting ) so that and for every . An edge set is an edge-cover of if for every there is an edge in from to . We show that minimal edge-covers of can be listed with polynomial delay, provided that, for any the minimal member of the residual family of the sets in not covered by can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal -connected and -outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time. [Copyright &y& Elsevier]

We consider a game-theoretical variant of the Steiner forest problem in which each player j, out of a set of k players, strives to connect his terminal pair (sj, tj ) of vertices in an undirected, edge-weighted graph G. In this paper we show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein, and Ravi [SIAM J. Comput., 24 (1995), pp. 445-456] yields a 2-budget balanced and cross-monotonic cost sharing method for this game. We also present a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree game. This shows that our result is tight. Our algorithm gives rise to a new linear programming relaxation for the Steiner forest problem which we term the lifted-cut relaxation. We show that this new relaxation is stronger than the standard undirected cut relaxation for the Steiner forest problem. [ABSTRACT FROM AUTHOR]

Abstract: A natural 3D extension of the Steiner chains problem, original to the authors of this article, where circles are substituted by spheres, is presented. Given three spheres such that either two of them are contained in (or intersect) the third one, chains of spheres, each one externally tangent to its two neighbors in the chain and to the first and second given spheres, and internally tangent to the third given sphere, are considered. A condition for these chains to be closed has been stated and the Steiner alternative or Steiner porism has been extended to 3D. Remarkably, the process is of symbolic-numeric nature. Using a computer algebra system is almost a must, because a theorem in the constructive theory in the background requires using the explicit general solution of a non-linear algebraic system. However, obtaining a particular solution requires computing concatenated processes involving trigonometric expressions. In this case, it is recommended to use approximated calculations to avoid obtaining huge expressions. [Copyright &y& Elsevier]

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V (G), and a positive cost ce for each edge e of G, finding a minimum-cost tree in G that contains at least one vertex from each R ∈ R. We call the sets in R groups. The well-known Steiner tree problem is the special case of the group Steiner tree problem in which each set in R is unitary. In this paper, we present a general reduction test designed to remove group vertices, that is, vertices belonging to some group. Through the use of these tests we can conclude that a given group vertex can be considered a nonterminal and hence can be removed from its group. We also present some computational results on instances from SteinLib [T. Koch, A. Martin, and S. Voss, SteinLib: An updated library on Steiner tree problems in graphs, in Steiner Trees in Industry, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001, pp. 285-325]. [ABSTRACT FROM AUTHOR]

A Steiner triple system of order v, or STS( v), is a pair ( V, [InlineMediaObject not available: see fulltext.]) with V a set of v points and [InlineMediaObject not available: see fulltext.] 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, [InlineMediaObject not available: see fulltext.]), and STS( v), ( V, [InlineMediaObject not available: see fulltext.]), 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≥2 u−3. [ABSTRACT FROM AUTHOR]

In this paper, Krein J*-triple systems are introduced. It can be shown that any KH*-triple system ([15]) or KJ*-algebra ([16]) can be made into a triple system. We give a few examples of Krein J*-triple system which are also simple. We obtain some structure theorems on some simple Krein J*-triple systems. [ABSTRACT FROM AUTHOR]

The early research on regular graphs of the French mathematician Georges Brunel (1856–1900) is discussed. Brunel developed early graph terminology and started the French “applied” approach towards graph theory. [Copyright &y& Elsevier]

This paper proves that a triangulated graph is an outline triple system of even index if and only if it is an amalgamated triple system of even index. 2000 Mathematical Subject Classification: primary 05B07; secondary 05C99. [ABSTRACT FROM AUTHOR]

Four methods for constructing anti-Pasch Steiner triple systems are developed. The first generalises a construction of Stinson and Wei to obtain a general singular direct product construction. The second generalises the Bose construction. The third employs a construction due to Lu. The fourth employs Wilson-type inflation techniques using Latin squares having no subsquares of order 2. As a consequence of these constructions we are able to produce anti-Pasch systems of order v for v 31 or 7 (mod 18), for v a 49 (mod 72), and for many other values of v. [ABSTRACT FROM AUTHOR]