umu.sePublications
Change search
Refine search result
123 101 - 132 of 132
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.
  • 101. Lo, Allan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    F-Factors in Hypergraphs Via Absorption2015In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 31, no 3, p. 679-712Article in journal (Refereed)
    Abstract [en]

    Given integers n ≥ k > l ≥ 1 and a k-graph F with |V(F)| divisible by n, define t k l (n, F) to be the smallest integer d such that every k-graph H of order n with minimum l-degree δl(H) ≥ d contains an F-factor. A classical theorem of Hajnal and Szemerédi in (Proof of a Conjecture of P. Erd˝os, pp. 601–623, 1969) implies that t2 1 (n, Kt) = (1 − 1/t)n for integers t. For k ≥ 3, t k k−1(n, Kk k ) (the δk−1(H) threshold for perfect matchings) has been determined by Kühn and Osthus in (J Graph Theory 51(4):269–280, 2006) (asymptotically) and Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009) (exactly) for large n. In this paper, we generalise the absorption technique of Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009) to F-factors. We determine the asymptotic values of t k 1 (n, Kk k (m)) for k = 3, 4 and m ≥ 1. In addition, we show that for t > k = 3 and γ > 0, t3 2 (n, K3 t ) ≤ (1− 2 t2−3t+4 +γ )n provided n is large and t|n. We also bound t 3 2 (n, K3 t )from below. In particular, we deduce that t 3 2 (n, K3 4 ) = (3/4+o(1))n answering a question of Pikhurko in (Graphs Combin 24(4):391–404, 2008). In addition, we prove that t k k−1(n, Kk t ) ≤ (1 − t−1 k−1 −1 + γ )n for γ > 0, k ≥ 6 and t ≥ (3 + √ 5)k/2 provided n is large and t|n.

  • 102. Lo, Allan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    l-Degree Turan Density2014In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 28, no 3, p. 1214-1225Article in journal (Refereed)
    Abstract [en]

    Let H-n be a k-graph on n vertices. For 0 <= l < k and an l-subset T of V (H-n), define the degree deg(T) of T to be the number of (k - l)-subsets S such that S boolean OR T is an edge in H-n. Let the minimum l-degree of H-n be delta(l) (H-n) = min{deg(T) : T subset of V (H-n) and vertical bar T vertical bar = l}. Given a family F of k-graphs, the l-degree Turan number ex(l) (n, F) is the largest delta(l) (H-n) over all F-free k-graphs H-n on n vertices. Hence, ex(0) (n, F) is the Turan number. We define l-degree Turan density to be pi(kappa)(l) (F) = lim sup(n ->infinity) ex(l)(n, F)/kappa(n-l). In this paper, we show that for k > l > 1, the set of pi(kappa)(l) (F) is dense in the interval [0, 1). Hence, there is no "jump" for l-degree Turan density when k > l > 1. We also give a lower bound on pi(kappa)(l) (F) in terms of an ordinary Turan density.

  • 103. Lo, Allan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Minimum codegree threshold for (K-4(3)-e)-factors2013In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 120, no 3, p. 708-721Article in journal (Refereed)
    Abstract [en]

    Given hypergraphs H and F, an F-factor in H is a spanning subgraph consisting of vertex-disjoint copies of F. Let K-4(3) - e denote the 3-uniform hypergraph on 4 vertices with 3 edges. We Show that for any gamma > 0 there exists an integer n(0) such that every 3-uniform hypergraph H of order n > n(0) with minimum codegree at least (1/2 + gamma)n and 4 vertical bar n contains a (K-4(3) - e)-factor. Moreover, this bound is asymptotically the best possible and we further give a conjecture on the exact value of the threshold for the existence of a (K-4(3) - e)-factor. Thereby, all minimum codegree thresholds for the existence of F-factors are known asymptotically for 3-uniform hypergraphs F on 4 vertices. (C) 2012 Elsevier Inc. All rights reserved.

  • 104.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Perfect matchings in 3-partite 3-uniform hypergraphs2014In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 127, p. 22-57Article in journal (Refereed)
    Abstract [en]

    Let H be a 3-partite 3-uniform hypergraph, i.e. a 3-uniform hypergraph such that every edge intersects every partition class in exactly one vertex, with each partition class of size n. We determine a Dirac-type vertex degree threshold for perfect matchings in 3-partite 3-uniform hypergraphs.

  • 105. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials2006In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, no 3, p. 343-353Article in journal (Refereed)
    Abstract [en]

    This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on epsilon(G), the average size of a broken-cycle-free subgraph of the graph G, whose behavior under edge deletion and contraction is studied.

  • 106. Lundow, P. H.
    et al.
    Rosengren, A.
    On the p, q-binomial distribution and the Ising model2010In: PHILOSOPHICAL MAGAZINE, Vol. 90, no 24, p. 3313-3353, article id PII 923766914Article in journal (Refereed)
    Abstract [en]

    We employ p, q-binomial coefficients, a generalisation of the binomial coefficients, to describe the magnetisation distributions of the Ising model. For the complete graph this distribution corresponds exactly to the limit case p = q. We apply our investigation to the simple d-dimensional lattices for d = 1, 2, 3, 4, 5 and fit p, q-binomial distributions to our data, some of which are exact but most are sampled. For d = 1 and d = 5, the magnetisation distributions are remarkably well-fitted by p,q-binomial distributions. For d = 4 we are only slightly less successful, while for d = 2, 3 we see some deviations (with exceptions!) between the p, q-binomial and the Ising distribution. However, at certain temperatures near Tc the statistical moments of the fitted distribution agree with the moments of the sampled data within the precision of sampling. We begin the paper by giving results of the behaviour of the p, q-distribution and its moment growth exponents given a certain parameterisation of p, q. Since the moment exponents are known for the Ising model (or at least approximately for d = 3) we can predict how p, q should behave and compare this to our measured p, q. The results speak in favour of the p, q-binomial distribution's correctness regarding its general behaviour in comparison to the Ising model. The full extent to which they correctly model the Ising distribution, however, is not settled.

  • 107. Lundow, Per Håkan
    et al.
    Rosengren, Anders
    The p,q-binomial distribution applied to the 5d Ising model2013In: PHILOSOPHICAL MAGAZINE, Vol. 93, no 14, p. 1755-1770Article in journal (Refereed)
    Abstract [en]

    The leading order form of the magnetization distribution is well-known for the 5d Ising model close to . Its corrections-to-scaling are not known though. Since we have earlier established that this distribution is extremely well-fitted by a -binomial distribution, we report considerably longer series expansions for its moments in terms of three parameters, providing new details on the scaling behaviour of the Ising distribution and its moments near . As applications, we give for example the scaling formulas for the ratios , and the full distribution at .

  • 108.
    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.

  • 109.
    Lundow, Per-Håkan
    et al.
    KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms2008In: LMS Journal of Computation and Mathematics, ISSN 1461-1570, E-ISSN 1461-1570, Vol. 11, p. 1-14Article in journal (Refereed)
    Abstract [en]

    The aim of this paper is to extend the previous work on transfer matrix compression in the case of graph homomorphisms. For H-homomorphisms of lattice-like graphs we demonstrate how the automorphisms of H, as well as those of the underlying lattice, can be used to reduce the size of the relevant transfer matrices. As applications of this method we give currently best known bounds for the number of 4- and 5-colourings of the square grid, and the number of 3- and 4-colourings of the three-dimensional cubic lattice. Finally, we also discuss approximate compression of transfer matrices.

  • 110.
    Lönnman, Magnus
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Eulerska grafer: egenskaper och tillämpningar2012Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
    Abstract [sv]

    Denna uppsats handlar om de så kallade eulerska graferna och grafer nära besläktade med dessa. En eulersk graf är en graf där det går att traversera alla kanter i grafen så att varje kant förekommer exakt en gång i traverseringen. Den struktur dessa grafer har uppfyller de villkor Euler ställde upp 1735 då han studerade det klassiska problemet med de sju broarna i Königsberg. Både teoretiska aspekter, som cykeldekomposition och kompatibla eulervägar, samt praktiska tillämpningar, som det kinesiska brevbärarproblemet och DNA-sekvensering (där man använder en de Bruijn-graf) behandlas i den här texten. Här redogörs även för kända och mindre kända metoder för enumeration av eulerska och semieulerska grafer. Dessa innefattar enumeration med hjälp av explicita formler, genererande funktioner samt algoritmiskt via generering. Tabeller med antal grafer presenteras för olika varianter av eulerska grafer (märkta, omärkta, planära etc.). Vid omärkt enumeration används endast den algoritmiska metoden, vilken också har använts för att generera och visa alla eulerska och semieulerska grafer med sju kanter, både enkla grafer och multigrafer.

  • 111.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Complete minors in cubic graphs with few short cycles and random cubic graphs2004In: Ars combinatoria, ISSN 0381-7032, Vol. 70, p. 289-295Article in journal (Refereed)
    Abstract [en]

    We first prove that for any fixed kappa a cubic graph with few short cycles contains a K-kappa-minor. This is a direct generalisation of a result on girth by Thomassen. We then use this theorem to show that for any fixed k a random cubic graph contains a Kk-minor asymptotically almost surely.

  • 112.
    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.

  • 113.
    Markström, Klas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Rucinski, Andrzej
    Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees2011In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 32, no 5, p. 677-687Article in journal (Refereed)
    Abstract [en]

    We establish a new lower bound on the l-wise collective minimum degree which guarantees the existence of a perfect matching in a k-uniform hypergraph, where 1 <= l < k/2. For l = 1, this improves a long-standing bound of Daykin and Haggkvist (1981) [5]. Our proof is a modification of the approach of Han et al. (2009) from [12]. In addition, we fill a gap left by the results solving a similar question for the existence of Hamilton cycles. (C) 2011 Published by Elsevier Ltd

  • 114.
    Markström, Klas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Thomason, Andrew
    Wagner, Peter
    Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree2011In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 27, no 2, p. 243-249Article in journal (Refereed)
    Abstract [en]

    The smallest n such that every colouring of the edges of K (n) must contain a monochromatic star K (1,s+1) or a properly edge-coloured K (t) is denoted by f (s, t). Its existence is guaranteed by the ErdAs-Rado Canonical Ramsey theorem and its value for large t was discussed by Alon, Jiang, Miller and Pritikin (Random Struct. Algorithms 23:409-433, 2003). In this note we primarily consider small values of t. We give the exact value of f (s, 3) for all s a parts per thousand yen 1 and the exact value of f (2, 4), as well as reducing the known upper bounds for f (s, 4) and f (s, t) in general.

  • 115.
    Markström, Klas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Unavoidable arrays2010In: Contributions to Discrete Mathematics, ISSN 1715-0868, E-ISSN 1715-0868, Vol. 5, no 1, p. 90-106Article in journal (Refereed)
    Abstract [en]

    An n x n array is avoidable if for each set of n symbols there is a Latin square on these symbols which diers from the array in every cell. We characterise all unavoidable square arrays with at most 2 symbols, and all unavoidable arrays of order at most 4. We also identify a number of general families of unavoidable arrays, which we conjecture to be a complete account of unavoidable arrays. Next, we investigate arrays with multiple entries in each cell, and identify a number of families of unavoidable multiple entry arrays. We also discuss fractional Latin squares, and their connections to unavoidable arrays.

    We note that when rephrasing our results as edge list-colourings of complete bipartite graphs, we have a situation where the lists of available colours are shorter than the length guaranteed by Galvin's Theorem to allow proper colourings.

  • 116.
    Nilson, Tomas
    et al.
    Mittuniversitetet.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Triple arrays and Youden squares2015In: Designs, Codes and Cryptography, ISSN 0925-1022, E-ISSN 1573-7586, Vol. 75, no 3, p. 429-451Article in journal (Refereed)
    Abstract [en]

    This paper addresses the question of when triple arrays can be constructed from Youden squares by removing a column together with the symbols therein, and then exchanging the role of columns and symbols. The scope of the investigation is limited to the standard case of triple arrays with $v=r+c-1$. For triple arrays with $\lambda_{cc}=1$ it is proven that they can never be     constructed in this way, and for triple arrays with $\lambda_{cc}=2$ it is proven that there always exists a suitable Youden square and a suitable column for this construction. Further, it is proven that Youden square constructed from a certain family of difference sets never give rise to triple arrays in this way but always gives rise to double arrays. Finally, it is proven that all triple arrays in the single known infinite family, the Paley triple arrays, can all be constructed in this way for some suitable choice of Youden square and column.

  • 117.
    Olsson, Christoffer
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Discreet Discrete Mathematics: Secret Communication Using Latin Squares and Quasigroups2017Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
    Abstract [en]

    This thesis describes methods of secret communication based on latin squares and their close relative, quasigroups. Different types of cryptosystems are described, including ciphers, public-key cryptosystems, and cryptographic hash functions. There is also a chapter devoted to different secret sharing schemes based on latin squares. The primary objective is to present previously described cryptosystems and secret sharing schemes in a more accessible manner, but this text also defines two new ciphers based on isotopic latin squares and reconstructs a lost proof related to row-latin squares.

  • 118.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On avoiding and completing colorings2019Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    All of my papers are related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend φ to a proper edge coloring of G which avoids L? 

    In Paper I, G is the d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. Paper II still deals with the hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most d-1 edges. In Paper III, G is a (d,s)-edge colorable graph; that is G has a proper d-edge coloring, where every edge is contained in at least s-1 2-colored 4-cycles, L must satisfy certain sparsity conditions and we do not have a partial proper edge precoloring φ on edges of G. The problem in Paper III is also considered in Paper IV and Paper V, but here G can be seen as the complete 3-uniform 3-partite hypergraph K3n,n,n, where n is a power of two in paper IV and n is an even number in paper V.

  • 119.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On avoiding and completing edge colorings2018Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    These papers are all related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend the precoloring to a proper edge coloring avoiding any list assignment? In the first paper, G is a d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and every list assignment L must satisfy certain sparsity conditions. The second paper still deals with d-dimensional hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most (d - 1) edges. For the third paper, G can be seen as a complete 3-uniform 3-partite hypergraph, every list assignment L must satisfy certain sparsity conditions but we do not have a partial proper edge precoloring φ on edges of G. 

  • 120.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On restricted colorings of (d,s)-edge colorable graphsManuscript (preprint) (Other academic)
    Abstract [en]

    A cycle is 2-colored if its edges are properly colored by two distinct colors. A (d,s)-edge colorable graph G is a d-regular graph that admits a proper d-edge coloring in which every edge of G is in at least s−1 2-colored 4-cycles. Given a (d,s)-edge colorable graph G and a list assigment L of forbidden colors for the edges of G satisfying certain sparsity conditions, we prove that there is a proper d-edge coloring of Gthat avoids L, that is, a proper edge coloring φ of G such that φ(e)∉L(e) for every edge e of G.

  • 121.
    Richter, Dirk
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Goldengorin, Boris
    Faculty of Economic Sciences, University of Groningen, The Netherlands, University of Economics and Business, Lviv Highway 51/2, 29016 Khmelnitsky, Ukraine and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Jäger, Gerold
    Department of Computer Science, Washington University, USA.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP2007In: Proceedings of the 4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007) / [ed] J. Janssen and P. Pralat, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007, p. 99-111Conference paper (Refereed)
    Abstract [en]

    Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.

  • 122. Riener, Cordian
    et al.
    Theobald, Thorsten
    Jansson Andren, Lina
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Lasserre, Jean B.
    Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization2013In: Mathematics of Operations Research, ISSN 0364-765X, E-ISSN 1526-5471, Vol. 38, no 1, p. 122-141Article in journal (Refereed)
    Abstract [en]

    In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semidefinite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited, and also propose some methods to efficiently compute the geometric quotient.

  • 123.
    Shcherbak, Denys
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Enumerative approaches and structural results for selected combinatorial problems2019Doctoral thesis, comprehensive summary (Other academic)
  • 124.
    Shcherbak, Denys
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Jäger, Gerold
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The Zero Forcing Number of Bijection Graphs2015In: Proceedings of 26th International Workshop om Combinatorial Algorithms (IWOCA 2015), Berlin-Heidelberg: Springer, 2015, Vol. 9538, p. 334-345Conference paper (Refereed)
    Abstract [en]

    The zero forcing number of a graph is a graph parameter based on a color change process, which starts with a state, where all vertices are colored either black or white. In the next step a white vertex turns black, if it is the only white neighbor of some black vertex, and this step is then iterated. The zero forcing number Z(G) is defined as the minimum cardinality of a set S of black vertices such that the whole vertex set turns black.

    In this paper we study Z(G) for the class of bijection graphs, where a bijection graph is a graph on 2n vertices that can be partitioned into two parts with n vertices each, joined by a perfect matching. For this class of graphs we show an upper bound for the zero forcing number and classify the graphs that attain this bound. We improve the general lower bound for the zero forcing number, which is Z(G)&#x2265;&#x03B4;(G)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Z(G)≥δ(G)Z(G)≥δ(G), for certain bijection graphs and use this improved bound to find the exact value of the zero forcing number for these graphs. This extends and strengthens results of Yi (2012) about the more restricted class of so called permutation graphs.

  • 125.
    Sjöström, Tomas
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Discrete time variational mechanics of multidomain systems: Applications to coupled electronic, hydraulic, and multibody systems2012Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Today there exist few non-smooth multi-domain simulation tools using time-discretized Lagrangian mechanics for circuits.The main goal is to show that itis possible to use a semi-implicit, parameter free non-smooth variational timestepper to simulate the circuits with time-steps proportional to the system timescales.This is demonstrated by implementing and performing extensive numericaltests for various types of electrical, mechanical and hydraulic components anddemonstrate that the components are stable, with the correct behavior whenthe system is solved using a modified block pivot solver.Simulation results shows that piecewise linear models are enough for thesimple switching circuits in this thesis.

  • 126. Trotignon, Nicolas
    et al.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    chi-bounds, operations, and chords2018In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, no 2, p. 312-336Article in journal (Refereed)
    Abstract [en]

    A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an O(n4m) time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most O(3) colors, where is the maximum number of pairwise adjacent vertices in G.

  • 127.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    A Note on Completing Partial Latin Squares2009In: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 45, p. 117-124Article in journal (Refereed)
  • 128.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin Squares with Prescriptions and Restrictions2011In: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 51, p. 77-87Article in journal (Refereed)
  • 129.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of mathematics.
    List colorings of graphs: a short survey2000Independent thesis Advanced level (degree of Master (One Year)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    We present an overview of the current state of the List Chromatic Conjecture (LCC) and results on the choice number of planar graphs, as well as of general progress on the subject of list colorings.

  • 130.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Partial latin squares are avoidable2011In: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 15, no 3, p. 485-497Article in journal (Refereed)
    Abstract [en]

    A square array is avoidable if for each set of n symbols there is an n x n Latin square on these symbols which differs from the array in every cell. The main result of this paper is that for m >= 2 any partial Latin square of order 4m - 1 is avoidable, thus concluding the proof that any partial Latin square of order at least 4 is avoidable.

  • 131.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The intricacy of avoiding arrays2005Manuscript (preprint) (Other academic)
  • 132.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The intricacy of avoiding arrays is 22006In: Discrete Mathematics, ISSN 0012-365X, Vol. 306, p. 531-532Article in journal (Refereed)
123 101 - 132 of 132
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