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]

It is conjectured that for every pair ( ℓ , m ) of odd integers greater than 2 with m ≡ 1 ( mod ℓ ) , there exists a cyclic two-factorization of K ℓ m having exactly ( m − 1 ) / 2 factors of type ℓ m and all the others of type m ℓ . The authors prove the conjecture in the affirmative when ℓ ≡ 1 ( mod 4 ) and m ≥ ℓ 2 − ℓ + 1 . [ABSTRACT FROM AUTHOR]

Abstract: The problem of identifying a single arbitrary edge in a graph using edge-identifying codes was recently considered by Foucaud et al. (in press) [4]. In this paper, we focus on locating more than one edge. First, we classify the graphs in which this is possible. Furthermore, for such graphs, we give a simple characterization of edge-identifying codes. Using the characterization, we give various lower and upper bounds for edge-identifying codes in terms of the order and size of a graph. In particular, codes with the minimum cardinality are obtained with the aid of 2-factors. In addition, we consider how the cardinality of the smallest edge-identifying codes behaves when an edge is added to a graph. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the relationship between -factors and component-deleted subgraphs of graphs. Let be a graph. A factor of is a complete-factor if every component of is complete. If is a complete-factor of , and is a component of , then is a component-deleted subgraph. Let denote the number of components of . Let be an integer-valued function defined on with even. Enomoto and Tokuda [H. Enomoto, T. Tokuda, Complete-factors and -factors, Discrete Math. 220 (2000) 239–242] proved that if is a complete-factor of with , and has an -factor for each component of , then has an -factor. We extend their result, and show that it suffices to consider a complete-factor of for some specified instead of . Let be a complete-factor of with . If has an -factor for each component of , then has an -factor in each of the following cases: (1) ; (2) is even and ; (3) has no isolated vertices and ; or (4) has no isolated vertices, is even and . We show that the results in this paper are sharp in some sense. [Copyright &y& Elsevier]

Abstract: We use discrete Morse theory to determine the Möbius function of generalized factor order. Ordinary factor order on the Kleene closure of a set is the partial order defined by letting if contains as a subsequence of consecutive letters. Generalized factor order takes into account a partial order on the alphabet , that is, whenever contains a subsequence such that for each , in . Using Babson and Hersh’s application of Robin Forman’s discrete Morse theory to poset order complexes, we are able to give a recursive formula for the Möbius function in the case where each element of covers a unique letter in . [Copyright &y& Elsevier]

Abstract: Let be a graph in which each vertex has been colored using one of colors, say . If an -cycle in has vertices colored , , and for every , then is equitably -colored. An -cycle decomposition of a graph is equitably -colorable if the vertices of can be colored so that every -cycle in is equitably -colored. For and 6, we completely settle the existence problem for equitably -colorable -cycle decompositions of complete graphs with the edges of a 1-factor added. [Copyright &y& Elsevier]

Abstract: We associate a signed digraph with a list of matrices whose dimensions permit them to be multiplied, and whose product is square. Cycles in this graph have a parity, that is, they are either even (termed e-cycles) or odd (termed o-cycles). The absence of e-cycles in the graph is shown to imply that the matrix product is a -matrix, i.e., all of its principal minors are nonnegative. Conversely, the presence of an e-cycle is shown to imply that there exists a list of matrices associated with the graph whose product fails to be a -matrix. The results generalise a number of previous results relating - and -matrices to graphs. [Copyright &y& Elsevier]

Abstract: Let be an integer and a bipartite graph with such that . In this paper it has been proved that if for each pair of nonadjacent vertices and , , then for any independent edges of , has a 2-factor with cycles such that and for each . We shall also show that the conditions in this paper are sharp. [Copyright &y& Elsevier]

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: In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218–224] we show the following. There exists a real number such that for every integer there exists an integer such that every Hamiltonian graph G of order with has a 2-factor with k components. [Copyright &y& Elsevier]

Abstract: In the most general sense, a factor of a graph G is just a spanning subgraph of G and a graph factorization of G is a partition of the edges of G into factors. However, as we shall see in the present paper, even this extremely general definition does not capture all the factor and factorization problems that have been studied in graph theory. Several previous survey papers have been written on this subject [F. Chung, R. Graham, Recent results in graph decompositions, London Mathematical Society, Lecture Note Series, vol. 52, Cambridge University Press, 1981, pp. 103–123; J. Akiyama, M. Kano, Factors and factorizations of graphs—a survey, J. Graph Theory 9 (1985) 1–42; L. Volkmann, Regular graphs, regular factors, and the impact of Petersen''s theorems, Jahresber. Deutsch. Math.-Verein. 97 (1995) 19–42] as well as an entire book on graph decompositions [J. Bosák, Decompositions of Graphs, Kluwer Academic Publishers Group, Dordrecht, 1990]. Our purpose here is to concentrate primarily on surveying the developments of the last 15–20 years in this exponentially growing field. [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]

Abstract: Let and be two integers. Suppose that G is a 2-edge-connected graph of order with minimum degree at least a. Then G has a 2-edge-connected -factor if every pair of non-adjacent vertices has degree sum at least . This lower bound is sharp. As a consequence, we have Ore-type conditions for the existence of a 2-edge-connected -factor in graphs. [Copyright &y& Elsevier]

We discuss a special case of the Hamilton–Waterloo problem in which a 2-factorization of Kn is sought consisting of 2-factors of two kinds: Hamiltonian cycles, and triangle-factors. We determine completely the spectrum of solutions for several infinite classes of orders n. [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]