Search

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]

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: 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]

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: 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]

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]

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]

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]