umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Häggkvist, Roland
Publications (10 of 14) Show all publications
Casselgren, C. J. & Häggkvist, R. (2016). Coloring Complete and Complete Bipartite Graphs from Random Lists. Graphs and Combinatorics, 32(2), 533-542.
Open this publication in new window or tab >>Coloring Complete and Complete Bipartite Graphs from Random Lists
2016 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, 533-542 p.Article in journal (Refereed) Published
Abstract [en]

Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

Keyword
List coloring, Random list, Coloring from random lists, Complete graph, Complete bipartite graph
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-118388 (URN)10.1007/s00373-015-1587-5 (DOI)000371081000007 ()
Available from: 2016-04-22 Created: 2016-03-18 Last updated: 2017-11-30Bibliographically approved
Fleischner, H. & Häggkvist, R. (2015). Cycle double covers containing certain circuits in cubic graphs having special structures. Discrete Mathematics, 338(10), 1750-1754.
Open this publication in new window or tab >>Cycle double covers containing certain circuits in cubic graphs having special structures
2015 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 338, no 10, 1750-1754 p.Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
Elsevier, 2015
Keyword
Circuit double covers, Cycle double covers, Cubic graphs
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-106761 (URN)10.1016/j.disc.2014.11.021 (DOI)000358092000013 ()
Available from: 2015-08-20 Created: 2015-08-07 Last updated: 2017-12-04Bibliographically approved
Fleischner, H. & Häggkvist, R. (2014). Cycle double covers in cubic graphs having special structures. Journal of Graph Theory, 77(2), 158-170.
Open this publication in new window or tab >>Cycle double covers in cubic graphs having special structures
2014 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 77, no 2, 158-170 p.Article in journal (Refereed) Published
Abstract [en]

In the first part of this article, we employ Thomason's Lollipop Lemma [25] to prove that bridgeless cubic graphs containing a spanning lollipop admit a cycle double cover (CDC) containing the circuit in the lollipop; this implies, in particular, that bridgeless cubic graphs with a 2-factor F having two components admit CDCs containing any of the components in the 2-factor, although it need not have a CDC containing all of F. As another example consider a cubic bridgeless graph containing a 2-factor with three components, all induced circuits. In this case, two of the components may separately be used to start a CDC although it is uncertain whether the third component may be part of some CDC. Numerous other corollaries shall be given as well. In the second part of the article, we consider special types of bridgeless cubic graphs for which a prominent circuit can be shown to be included in a CDC. The interest here is the proof technique and therefore we only give the simplest case of the theorem. Notably, we show that a cubic graph that consists of an induced 2k-circuit C together with an induced 4k-circuit T and an independent set of 2k vertices, each joined by one edge to C and two edges to T, has a CDC starting with T.

Keyword
CDC, Lollipop
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-94547 (URN)10.1002/jgt.21779 (DOI)000341710300005 ()
Available from: 2014-11-06 Created: 2014-10-13 Last updated: 2017-12-05Bibliographically approved
Casselgren, C. J. & Häggkvist, R. (2013). Completing partial Latin squares with one filled row, column and symbol. Discrete Mathematics, 313(9), 1011-1017.
Open this publication in new window or tab >>Completing partial Latin squares with one filled row, column and symbol
2013 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 313, no 9, 1011-1017 p.Article in journal (Refereed) Published
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.

Keyword
Latin square, Partial Latin square, Completing partial Latin squares
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-71068 (URN)10.1016/j.disc.2013.01.019 (DOI)000317327200005 ()
Available from: 2013-06-18 Created: 2013-05-20 Last updated: 2017-12-06Bibliographically approved
Fleischner, H. & Häggkvist, R. (2009). Circuit double covers in special types of cubic graphs. Discrete Mathematics, 309(18), 5724-5728.
Open this publication in new window or tab >>Circuit double covers in special types of cubic graphs
2009 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 309, no 18, 5724-5728 p.Article in journal (Refereed) Published
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.

Keyword
Circuit double cover; Hypohamiltonian cubic graphs
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-22716 (URN)10.1016/j.disc.2008.05.018 (DOI)
Available from: 2009-05-15 Created: 2009-05-15 Last updated: 2017-12-13Bibliographically approved
Häggkvist, R., Rosengren, A., Lundow, P. H., Markström, K., Andrén, D. & Kundrotas, P. (2007). On the Ising model for the simple cubic lattice. Advances in Physics, 56(5), 653-755.
Open this publication in new window or tab >>On the Ising model for the simple cubic lattice
Show others...
2007 (English)In: Advances in Physics, ISSN 0001-8732, E-ISSN 1460-6976, Vol. 56, no 5, 653-755 p.Article, review/survey (Refereed) Published
Abstract [en]

The Ising model was introduced in 1920 to describe a uniaxial system of magnetic moments, localized on a lattice, interacting via nearest-neighbour exchange interaction. It is the generic model for a continuous phase transition and arguably the most studied model in theoretical physics. Since it was solved for a two-dimensional lattice by Onsager in 1944, thereby representing one of the very few exactly solvable models in dimensions higher than one, it has served as a testing ground for new developments in analytic treatment and numerical algorithms. Only series expansions and numerical approaches, such as Monte Carlo simulations, are available in three dimensions. This review focuses on Monte Carlo simulation. We build upon a data set of unprecedented size. A great number of quantities of the model are estimated near the critical coupling. We present both a conventional analysis and an analysis in terms of a Puiseux series for the critical exponents. The former gives distinct values of the high- and low-temperature exponents; by means of the latter we can get these exponents to be equal at the cost of having true asymptotic behaviour being found only extremely close to the critical point. The consequences of this for simulations of lattice systems are discussed at length.

Place, publisher, year, edition, pages
Taylor & Francis, 2007
National Category
Physical Sciences
Identifiers
urn:nbn:se:umu:diva-8259 (URN)10-1080/00018730701577548 (DOI)000249988600001 ()
Available from: 2008-01-15 Created: 2008-01-15 Last updated: 2017-12-14Bibliographically approved
Häggkvist, R. & Markström, K. (2006). Cycle double covers and spanning minors I. Journal of combinatorial theory. Series B (Print), 96(2), 183-206.
Open this publication in new window or tab >>Cycle double covers and spanning minors I
2006 (English)In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 96, no 2, 183-206 p.Article in journal (Refereed) Published
Abstract [en]

Define a graph to be a Kotzig graph if it is $m$-regular and has an $m$-edge colouring in which each pair of colours form a Hamiltonian cycle. We show that every cubic graph with spanning subgraph consisting of a subdivision of a Kotzig graph together with even cycles has a cycle double cover, in fact a 6-CDC. We prove this for two other families of graphs similar to Kotzig graphs as well. In particular, let $F$ be a 2-factor in a cubic graph $G$ and denote by $G_{F}$ the pseudograph obtained by contracting each component in $F$. We show that if there exist a cycle in $G_{F}$ through all vertices of odd degree, then $G$ has a CDC. We conjecture that every 3-connected cubic graph contains a spanning subgraph homeomorphic to a Kotzig graph. In a sequel we show that every cubic graph with a spanning homeomorph of a 2-connected cubic graph on at most 10 vertices has a CDC.

Place, publisher, year, edition, pages
New York etc.: Academic Press, 2006
Keyword
Cycle double cover, Kotzig; Frame, Cubic graphs
Identifiers
urn:nbn:se:umu:diva-7660 (URN)10.1016/j.jctb.2005.07.004 (DOI)
Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2017-12-14Bibliographically approved
Häggkvist, R. & Markström, K. (2006). Cycle double covers and spanning minors II. Discrete Mathematics, 306(8-9), 762-778.
Open this publication in new window or tab >>Cycle double covers and spanning minors II
2006 (Swedish)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 306, no 8-9, 762-778 p.Article in journal (Refereed) Published
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].

Place, publisher, year, edition, pages
Amsterdam: North-Holland, 2006
Identifiers
urn:nbn:se:umu:diva-7649 (URN)10.1016/j.disc.2005.10.031 (DOI)
Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2017-12-14Bibliographically approved
Häggkvist, R., Rosengren, A., Andrén, D., Kundrotas, P., Lundow, P.-H. & Markström, K. (2004). A Monte Carlo sampling scheme for the Ising model. Journal of statistical physics, 114(1-2), 455-480.
Open this publication in new window or tab >>A Monte Carlo sampling scheme for the Ising model
Show others...
2004 (English)In: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 114, no 1-2, 455-480 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we describe a Monte Carlo sampling scheme for the Ising model and similar discrete-state models. The scheme does not involve any particular method of state generation but rather focuses on a new way of measuring and using the Monte Carlo data. We show how to reconstruct the entropy S of the model, from which, e.g., the free energy can be obtained. Furthermore we discuss how this scheme allows us to more or less completely remove the effects of critical fluctuations near the critical temperature and likewise how it reduces critical slowing down. This makes it possible to use simple state generation methods like the Metropolis algorithm also for large lattices.

Place, publisher, year, edition, pages
Springer, 2004
Keyword
Monte Carlo methods, density of states, microcanonical
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-2346 (URN)10.1023/B:JOSS.0000003116.17579.5d (DOI)000186548300016 ()
Available from: 2007-05-10 Created: 2007-05-10 Last updated: 2017-12-14Bibliographically approved
Häggkvist, R. & Johansson, R. (2004). A note on edge-decompositions of planar graphs. Discrete Mathematics, 283(1-3), 263-266.
Open this publication in new window or tab >>A note on edge-decompositions of planar graphs
2004 (English)In: Discrete Mathematics, ISSN 0012-365X, Vol. 283, no 1-3, 263-266 p.Article in journal (Refereed) Published
Identifiers
urn:nbn:se:umu:diva-9018 (URN)
Available from: 2008-02-26 Created: 2008-02-26Bibliographically approved
Organisations

Search in DiVA

Show all publications