| 1. |
- Leader, Imre, et al.
(författare)
-
Uncountable families of vertex-transitive graphs of finite degree
- 2006
-
Ingår i: Discrete Mathematics. ; 306:7, s. 678-679
-
Tidskriftsartikel (refereegranskat)abstract
- Recently the following question was relayed to the second author: What is the cardinality of the set of vertex transitive graphs of finite degree? Our aim in this short note is to show that there are $2^{\aleph_{0}}$ such graphs.
|
|
| 2. |
- Casselgren, Carl Johan, et al.
(författare)
-
Edge precoloring extension of hypercubes
- 2020
-
Ingår i: Journal of Graph Theory. - : John Wiley & Sons. - 0364-9024 .- 1097-0118. ; 95:3, s. 410-444
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of extending partial edge colorings of hypercubes. In particular, we obtain an analogue of the positive solution to the famous Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most d − 1 edges of the d‐dimensional hypercube Qd can be extended to a proper d‐edge coloring of Qd. Additionally, we characterize which partial edge colorings of Qd with precisely d precolored edges are extendable to proper d‐edge colorings of Qd.
|
|
| 3. |
|
|
| 4. |
- Casselgren, Carl Johan, et al.
(författare)
-
Latin cubes with forbidden entries
- 2019
-
Ingår i: The Electronic Journal of Combinatorics. - Newark : Department of Mathematical Science, University of Delaware. - 1097-1440 .- 1077-8926. ; 26:1
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant y>0 such that if n=2k and A is a 3-dimensional n×n×n array where every cell contains at most γn symbols, and every symbol occurs at most γn times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 ≤ i,j,k ≤ n, the symbol in position (i,j,k) of L does not appear in the corresponding cell of A.
|
|
| 5. |
- Casselgren, Carl Johan, et al.
(författare)
-
Restricted extension of sparse partial edge colorings of hypercubes
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions.
|
|
| 6. |
- Falgas-Ravry, Victor, et al.
(författare)
-
Speed and concentration of the covering time for structured coupon collectors
- 2020
-
Ingår i: Advances in Applied Probability. - : Cambridge University Press. - 0001-8678 .- 1475-6064. ; 52:2, s. 433-462
-
Tidskriftsartikel (refereegranskat)abstract
- Let V be an n-set, and let X be a random variable taking values in the powerset of V. Suppose we are given a sequence of random coupons X1,X2,…, where the Xi are independent random variables with distribution given by X. The covering time T is the smallest integer t≥0 such that ⋃ti=1Xi=V. The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed almost exclusively on the case where X is assumed to be symmetric and/or uniform in some way.In this paper we study the covering time for much more general random variables X; we give general criteria for T being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where T fails to be concentrated and when structural properties in the distribution of X allow for a very different behaviour of T relative to the symmetric/uniform case.
|
|
| 7. |
- Hägglund, Jonas, 1982-, et al.
(författare)
-
On stable cycles and cycle double covers of graphs with large circumference
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 312:17, s. 2540-2544
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 8. |
- Hägglund, Jonas, 1982-
(författare)
-
Snarks : Generation, coverings and colourings
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis. The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order.In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24.In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs. In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings.Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.
|
|
| 9. |
- Larsson, Joel, 1987-, et al.
(författare)
-
Biased random k-SAT
-
Annan publikation (övrigt vetenskapligt/konstnärligt)
|
|
| 10. |
- Larsson, Joel, 1987-, et al.
(författare)
-
Biased random k-SAT
- 2021
-
Ingår i: Random structures & algorithms (Print). - : John Wiley & Sons. - 1042-9832 .- 1098-2418. ; 59:2, s. 238-266
-
Tidskriftsartikel (refereegranskat)abstract
- The basic random k‐SAT problem is: given a set of n Boolean variables, and m clauses of size k picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive—that is, variables occur negated w.p. 0<p<½ and positive otherwise—and study how the satisfiability threshold depends on p. For p<½ this model breaks many of the symmetries of the original random k‐SAT problem, for example, the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed k, we find the asymptotics of the threshold as p approaches 0 or ½ . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.
|
|
