| 1. |
- Asratian, Armen S.
(författare)
-
Some results on an edge coloring problem of Folkman and Fulkerson
- 2000
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 223:1-3, s. 13-25
-
Tidskriftsartikel (refereegranskat)abstract
- In 1968, Folkman and Fulkerson posed the following problem: Let G be a graph and let (n1,...,nt) be a sequence of positive integers. Does there exist a proper edge coloring of G with colors 1,2,...,t such that precisely ni edges receive color i, for each i=1,...,t? If such a coloring exists then the sequence (n1,...,nt) is called color-feasible for G. Some sufficient conditions for a sequence to be color-feasible for a bipartite graph where found by Folkman and Fulkerson, and de Werra. In this paper we give a generalization of their results for bipartite graphs. Furthermore, we find a set of color-feasible sequences for an arbitrary simple graph. In particular, we describe the set of all sequences which are color-feasible for a connected simple graph G with Δ(G)3, where every pair of vertices of degree at least 3 are non-adjacent.
|
|
| 2. |
- Bränden, Petter, et al.
(författare)
-
Catalan continued fractions, and increasing subsequences in permutations
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 258:03-jan, s. 275-287
-
Tidskriftsartikel (refereegranskat)abstract
- We call a Stieltjes continued fraction with monic monomial numerators a Catalan continued fraction. Let e(k)(pi) be the number of increasing subsequences of length k + 1 in the permutation pi. We prove that any Catalan continued fraction is the multivariate generating function of a family of statistics on the 132-avoiding permutations, each consisting of a (possibly infinite) linear combination of the e(k)S. Moreover, there is an invertible linear transformation that translates between linear combinations of ekS and the corresponding continued fractions. Some applications are given, one of which relates fountains of coins to 132-avoiding permutations according to number of inversions. Another relates ballot numbers to such permutations according to number of right-to-left maxima.
|
|
| 3. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)abstract
- Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome, It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to [(2n - 2)/3] for n greater than or equal to 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely [(n + 1)/2]. Computations of Bafha and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player's case. Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.
|
|
| 4. |
- Eriksson, K., et al.
(författare)
-
Stable matching in a common generalization of the marriage and assignment models
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 217:3-Jan, s. 135-156
-
Tidskriftsartikel (refereegranskat)abstract
- In the theory of two-sided matching markets there are two well-known models: the marriage model (where no money is involved) and the assignment model (where payments are involved). Roth and Sotomayor, Two-Sided Matching, Cambridge University Press, Cambridge, 1990, asked for an explanation for the similarities in behavior between those two models. We address this question by introducing a common generalization that preserves the two important features: the existence of a stable outcome and the lattice property of the set of stable outcomes.
|
|
| 5. |
- Guibert, O., et al.
(författare)
-
Doubly alternating Baxter permutations are Catalan
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 217:03-jan, s. 157-166
-
Tidskriftsartikel (refereegranskat)abstract
- The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given.
|
|
| 6. |
- Heden, Olof, et al.
(författare)
-
Bruen chains in PG(3, p(k)) k >= 2
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 214:3-Jan, s. 251-253
-
Tidskriftsartikel (refereegranskat)abstract
- The Bruen chains of PC(3,q) for q = 9, 25 and 27 are described. They were found by a computer search. In the case q = 49 no chains have been found yet.
|
|
| 7. |
- Heden, Olof
(författare)
-
Maximal partial spreads and the modular n-queen problem III
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 243:3-Jan, s. 135-150
-
Tidskriftsartikel (refereegranskat)abstract
- Maximal partial spreads in PG(3, q) q = p(k), p odd prime and q greater than or equal to 7, are constructed for any integer n in the interval (q(2) + 1)/2 + 6 less than or equal to n less than or equal to (5q(2) + 4q - 1)/8 in the case q + 1 0, +/-2, +/-4, +/-6, +/-10, 12 (mod 24). In all these cases. maximal partial spreads of the size (q(2) + 2 + n have also been constructed for some small values of the integer n. These values depend on q and are mainly n = 3 and n = 4. Combining these results with previous results of the author and with that of others we can conclude that there exist maximal partial spreads in PG(3, q), q = p(k) where p is an odd prime and q greater than or equal to 7, of size n for any integer n in the interval (q(2) + 1) /2 + 6 less than or equal to n less than or equal to q(2) - q + 2.
|
|
| 8. |
- Heden, Olof
(författare)
-
On the reconstruction of perfect codes
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 256:2-Jan, s. 479-485
-
Tidskriftsartikel (refereegranskat)abstract
- We show how to reconstruct a perfect I-error correcting binary code of length n from the code words of weight (n + 1)/2.
|
|
| 9. |
- Huber, K. T., et al.
(författare)
-
The relation graph
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 244:1-3, s. 153-166
-
Tidskriftsartikel (refereegranskat)abstract
- Given a set R of distinct, non-trivial partitions of a finite set, we define the relation graph G(R) of R. In case R consists only of bipartitions, G(R) is the well-known Buneman graph, a median graph that has applications in the area of phylogenetic analysis., Here we consider properties of the relation graph for general sets of partitions and, in particular, we see that it mimics the behaviour of the Buneman graph by proving the following two theorems:(i) The graph G(R) is a Hamming graph if and only if R is strongly incompatible.(ii) The graph G(R) is a block graph with #R blocks if and only if R is strongly compatible.
|
|
| 10. |
- Linusson, Svante
(författare)
-
Extended pattern avoidance
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 246:1-3, s. 219-230
-
Tidskriftsartikel (refereegranskat)abstract
- A 0-1 matrix is said to be extendably tau-avoiding if it can be the upper left corner of a tau-avoiding permutation matrix. This concept arose in Eriksson and Linusson (Electron. J. Combin. 2 (1995) R6) where the surprising result that the number of extendably 321-avoiding rectangles are enumerated by the ballot numbers was proved, Here we study the other five patterns of length three. The main result is that the six patterns of length three divide into only two cases, no easy symmetry can explain this. Another result is that the Simion-Schmidt-West bijection for permutations avoiding patterns 12tau and 21tau works also for extended pattern avoidance. As an application, we use the results on extended pattern avoidance to prove a sequence of refinements on the enumeration of permutations avoiding patterns of length 3. The results and proofs use many properties and refinements of the Catalan numbers. (C) 2002 Elsevier Science B.V. All rights reserved.
|
|
