Search

We consider the problem of classifying trades in Steiner triple systems such that each block of the trade contains one of three fixed elements. We show that the fundamental building blocks for such trades are 3 -regular graphs that are 1 -factorisable. In the process we also generate all possible 2 - and 3 -way simultaneous edge colourings of graphs with maximum degree 3 using at most 3 colours, where multiple edges but not loops are allowed. Moreover, we generate all possible Latin trades within three rows. [ABSTRACT FROM AUTHOR]

Abstract: Let be a positive integer. It is shown that if is a graph of order with minimum degree at least , then contains vertex-disjoint copies of , unless is isomorphic to with being odd. [Copyright &y& Elsevier]

Abstract: We give lower and upper bounds on the total domination number of the cross product of two graphs, . These bounds are in terms of the total domination number and the maximum degree of the factors and are best possible. We further investigate cross products involving paths and cycles. We determine the exact values of and where and denote, respectively, a path and a cycle of length . [Copyright &y& Elsevier]

Abstract: A graph G is called -free if G has no induced subgraph isomorphic to . Let n, a, b be integers with , , and . We prove that every connected -free graph G has a connected -factor if G contains an -factor. This result is sharp in the sense that there exists a connected -free graph which has an -factor but no connected -factor for . [Copyright &y& Elsevier]

Semigraphoids are special sets of triples (I,J,K), I, J, K disjoint subsets of a finite set, that mimic conditional independences. New constructions on semigraphoids are introduced, the most crucial being factors and expansions. They are aimed at study of new classes of semigraphoids, that are constructed from semigraphoids of a trivial structure, e.g. from uniform semigraphoids, and at bringing each semigraphoid to a canonical form. Canonical semigraphoids are defined and each semigraphoid is constructed from a canonical one by means of a pure minor and an expansion. Semigraphoid closure and generators are investigated. The case of two generators is analysed in detail. Invariants for semigraphoids based on relations among generators are introduced and the corresponding classes of semigraphoids are related to classes built from uniform semigraphoids. Representability of semigraphoids by linear spaces and random variables is reexamined. The semigraphoids with at most two generators are proved to be linear and hence, by a simple lemma, probabilistic. [Copyright &y& Elsevier]