umu.sePublications
Change search
Refine search result
1 - 13 of 13
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Asratian, Armen S.
    et al.
    Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On interval edge colorings of (a,b)-biregular bipartitie graphs2006In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 307, no 15, p. 1951-1956Article in journal (Refereed)
  • 2.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On avoiding some families of arrays2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 5, p. 963-972Article in journal (Refereed)
    Abstract [en]

    An n×n array A with entries from {1,…,n} is avoidable if there is an n×n Latin square L such that no cell in L contains a symbol that occurs in the corresponding cell in A. We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is NP-complete, even in the case when the array has entries from only two distinct symbols. Assuming that PNP, this disproves a conjecture by Öhman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order n≥2k with entries from at most k distinct symbols and where each symbol occurs in at most n−2 cells is avoidable, and every single entry array of order n, where each of the symbols 1,…,n occurs in at most cells, is avoidable. Additionally, if k≥2, then every single entry array of order at least n≥4, where at most k rows contain non-empty cells and where each symbol occurs in at most nk+1 cells, is avoidable.

  • 3.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Vertex coloring complete multipartite graphs from random lists of size 22011In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, no 13, p. 1150-1157Article in journal (Refereed)
    Abstract [en]

    Let Ks×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of Ks×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all vV(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.

  • 4. Casselgren, Carl Johan
    et al.
    Häggkvist, Roland
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Completing partial Latin squares with one filled row, column and symbol2013In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 313, no 9, p. 1011-1017Article in journal (Refereed)
    Abstract [en]

    Let P be an n x n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbols. Assume further that s is the symbol of cell (r, c) in P. We prove that P is completable to a Latin square if n >= 8 and n is divisible by 4, or n <= 7 and n is not an element of {3, 4, 5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square. (C) 2013 Elsevier B.V. All rights reserved.

  • 5.
    Cutler, Jonathan
    et al.
    Umeå University, Faculty of Science and Technology, Department of mathematics. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA.
    Montagh, Balazs
    Unavoidable subgraphs of colored graphs2008In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 308, no 19, p. 4396-4413Article in journal (Refereed)
    Abstract [en]

    A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper. we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let y(k) be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K-k/2's or simply one K-k/2. Bollobas conjectured that for all k and epsilon > 0, there exists an n(k, epsilon) such that if n >= n(k, epsilon) then every two-edge-coloring of K-n, in which the density of each color is at least epsilon, contains a member of this family. We solve this conjecture and present a series of results bounding it (k, s) for different ranges of epsilon. In particular, if epsilon is sufficiently close to 1/2, the gap between out upper and lower bounds for n(k, epsilon) is smaller than those for the classical Ramsey number R(k, k).

  • 6. Fleischner, Herbert
    et al.
    Häggkvist, Roland
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Circuit double covers in special types of cubic graphs2009In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 309, no 18, p. 5724-5728Article in journal (Refereed)
    Abstract [en]

    Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that GV(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that Gv is hamiltonian for every vV(G)) have strong circuit double covers.

  • 7.
    Fleischner, Herbert
    et al.
    Institute for Information Systems, Technical University of Vienna, Wien, Austria.
    Häggkvist, Roland
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Cycle double covers containing certain circuits in cubic graphs having special structures2015In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 338, no 10, p. 1750-1754Article in journal (Refereed)
    Abstract [en]

    Our point of departure is Fleischner and Haggkvist (2014, Theorem 2). We first generalize this theorem. Then we apply it to cubic graphs whose vertex set can be decomposed into two classes, one class inducing a circuit and the other class inducing a (subdivision of a) caterpillar. (C) 2014 Elsevier B.V. All rights reserved.

  • 8.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Cycle double covers and spanning minors II2006In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 306, no 8-9, p. 762-778Article in journal (Refereed)
    Abstract [en]

    In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].

  • 9.
    Hägglund, Jonas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On stable cycles and cycle double covers of graphs with large circumference2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, p. 2540-2544Article in journal (Refereed)
    Abstract [en]

    A cycle C in a graph is called stable if there exists no other cycle D in the same graph such that V(C)⊆V(D). In this paper, we study stable cycles in snarks and we show that if a cubic graph G has a cycle of length at least |V(G)|−9 then it has a cycle double cover. We also give a construction for an infinite snark family with stable cycles of constant length and answer a question by Kochol by giving examples of cyclically 5-edge connected snarks with stable cycles.

  • 10.
    Lundow, Per-Håkan
    Umeå University, Faculty of Science and Technology, Department of mathematics.
    Compression of transfer matrices2001In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 231, no 1-3, p. 321-329Article in journal (Refereed)
    Abstract [en]

    We present a method for reducing the size of transfer matrices by exploiting symmetry. For example, the transfer matrix for enumeration of matchings in the graph C-4 x C-4 x P-n can be reduced from order 65536 to 402 simply due to the 384 automorphisms of C-4 x C-4. The matrix for enumeration of perfect matchings can be still further reduced to order 93, all in a straightforward and mechanical way. As an application we report an improved upper bound for the three-dimensional dimer problem. (C) 2001 Elsevier Science B.V. All rights reserved.

  • 11.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Even cycle decompositions of 4-regular graphs and line graphs2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, p. 2676-2681Article in journal (Refereed)
    Abstract [en]

    An even cycle decomposition of a graph is a partition of its edge into even cycles. We first give some results on the existence of even cycle decomposition in general 4-regular graphs, showing that K 5 is not the only graph in this class without such a decomposition. Motivated by connections to the cycle double cover conjecture we go on to consider even cycle decompositions of line graphs of 2-connected cubic graphs. We conjecture that in this class even cycle decompositions always exists and prove the conjecture for cubic graphs with oddness at most 2. We also discuss even cycle double covers of cubic graphs.

  • 12.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Extremal hypergraphs and bounds for the Turan density of the 4-uniform K-52009In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 309, no 16, p. 5231-5234Article in journal (Refereed)
    Abstract [en]

    In this paper we find, for n <= 16, the maximum number of edges in a 4-uniform hypergraph which does not have the complete 4-uniform hypergraph on five vertices, K-5(4), as a subgraph. Equivalently, we find all optimal (n, n-4, n-5) covering designs for n <= 16. Using these results we find a new upper bound for the Turin density of K-5(4). pi(K-5(4)) <= 1753/2380 = 0.73655.... Finally we make some notes on the structure of the extremal 4-graphs for this problem and the conjectured extremal family. (C) 2009 Published by Elsevier B.V.

  • 13.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On the intricacy of avoiding multiple-entry arrays2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 20, p. 3030-3036Article in journal (Refereed)
    Abstract [en]

    Let A be any n x n array on the symbols vertical bar n vertical bar = {1, . . . , n}, with at most in symbols in each cell. An n x n Latin square L on the symbols till is said to avoid A if no entry in L is present in the corresponding cell of A, and A is said to be avoidable if such a Latin square L exists. The intricacy of this problem is defined to be the minimum number of arrays into which A must be split in order to ensure that each part is avoidable. We present lower and upper bounds for the intricacy, and conjecture that the lower bound is in fact the correct answer. (C) 2012 Elsevier B.V. All rights reserved.

1 - 13 of 13
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf