| 1. |
- Adamaszek, Michal, et al.
(författare)
-
On a lower bound for the connectivity of the independence complex of a graph
- 2011
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 311:21, s. 2566-2569
-
Tidskriftsartikel (refereegranskat)abstract
- Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.
|
|
| 2. |
- Björklund, Johan, et al.
(författare)
-
Counterexamples to a monotonicity conjecture for the threshold pebbling number
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:15, s. 2401-2405
-
Tidskriftsartikel (refereegranskat)abstract
- Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move, in which two pebbles are removed from a vertex and one is placed on a neighbouring vertex. Given a graph G, the pebbling number pi (G) is the least t such that every initial distribution of t pebbles at the vertices of G is solvable, that is for every target vertex nu, there is some list of pebbling moves that ends with nu having a pebble. Given a graph sequence (G(n)), the pebbling threshold tau (G(n)) is a sequence (a(n)) such that t = a(n) is the smallest number of pebbles such that a random configuration of t pebbles on the vertices of G(n) is solvable with probability at least 1/2, in the probabilistic model where each configuration oft pebbles on the vertices of G(n) is selected uniformly at random. This paper provides counterexamples to the following monotonicity conjecture stated by Hurlbert et al.: If (G(n)) and (H-n) are graph sequences such that pi(G(n)) <= pi(H-n), then it holds that tau(G(n)) is an element of O(tau(H-n)).
|
|
| 3. |
- Casselgren, Carl Johan, et al.
(författare)
-
Completing partial Latin squares with one filled row, column and symbol
- 2013
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 313:9, s. 1011-1017
-
Tidskriftsartikel (refereegranskat)abstract
- Let P be an n×n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbol s. 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∉{3,4,5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square.
|
|
| 4. |
- Casselgren, Carl Johan, 1982-
(författare)
-
On avoiding some families of arrays
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:5, s. 963-972
-
Tidskriftsartikel (refereegranskat)abstract
- 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 P≠NP, 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 n−k+1 cells, is avoidable.
|
|
| 5. |
- Casselgren, Carl Johan, 1982-
(författare)
-
Vertex coloring complete multipartite graphs from random lists of size 2
- 2011
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 311:13, s. 1150-1157
-
Tidskriftsartikel (refereegranskat)abstract
- 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 v∈V(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.
|
|
| 6. |
- Heden, Olof
(författare)
-
A note on the symmetry group of full rank perfect binary codes
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:19, s. 2973-2977
-
Tidskriftsartikel (refereegranskat)abstract
- It is proved that the size of the symmetry group Sym(C) of every full rank perfect 1-error correcting binary code C of length n is less than or equal to 2|Sym( Hn)|(n+1), where Hn is a Hamming code of the same length.
|
|
| 7. |
- Heden, Olof
(författare)
-
On kernels of perfect codes
- 2010
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 310:21, s. 3052-3055
-
Tidskriftsartikel (refereegranskat)abstract
- It is shown that there exists a perfect one-error-correcting binary code with a kernel which is not contained in any Hamming code.
|
|
| 8. |
- Heden, Olof, et al.
(författare)
-
On the classification of perfect codes : Extended side class structures
- 2010
-
Ingår i: Discrete Mathematics. - Amsterdam, Netherlands : Elsevier. - 0012-365X .- 1872-681X. ; 310:1, s. 43-55
-
Tidskriftsartikel (refereegranskat)abstract
- The two 1-error correcting perfect binary codes, C and C′ are said to be equivalent if there exists a permutation π of the set of the n coordinate positions and a word such that . Hessler defined C and C′ to be linearly equivalent if there exists a non-singular linear map φ such that C′=φ(C). Two perfect codes C and C′ of length n will be defined to be extended equivalent if there exists a non-singular linear map φ and a word such thatHeden and Hessler, associated with each linear equivalence class an invariant LC and this invariant was shown to be a subspace of the kernel of some perfect code. It is shown here that, in the case of extended equivalence, the corresponding invariant will be the extension of the code LC.This fact will be used to give, in some particular cases, a complete enumeration of all extended equivalence classes of perfect codes.
|
|
| 9. |
- Heden, Olof
(författare)
-
On the size of the symmetry group of a perfect code
- 2011
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 311:17, s. 1879-1885
-
Tidskriftsartikel (refereegranskat)abstract
- It is shown that for every nonlinear perfect code C of length n and rank r with n - log(n + 1) + 1 <= r <= n - 1, vertical bar Sym(C)vertical bar <= vertical bar GL(n - r, 2)vertical bar . vertical bar GL(log(n +1) - (n - r), 2)vertical bar . (n + 1/2(n-r))(n-r) where Sym(C) denotes the group of symmetries of C. This bound considerably improves a bound of Malyugin. (C) 2011 Elsevier B.V. All rights reserved.
|
|
| 10. |
- Heden, Olof, et al.
(författare)
-
On the type(s) of minimum size subspace partitions
- 2014
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 332, s. 1-9
-
Tidskriftsartikel (refereegranskat)abstract
- Let V = V(kt + r, q) be a vector space of dimension kt + r over the finite field with q elements. Let sigma(q)(kt + r, t) denote the minimum size of a subspace partition P of V in which t is the largest dimension of a subspace. We denote by n(di) the number of subspaces of dimension d(i) that occur in P and we say [d(1)(nd1),..., d(m)(ndm)] is the type of P. In this paper, we show that a partition of minimum size has a unique partition type if t + r is an even integer. We also consider the case when t + r is an odd integer, but only give partial results since this case is indeed more intricate.
|
|
