| 1. |
- Huber, K. T., et al.
(author)
-
The relation graph
- 2002
-
In: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 244:1-3, s. 153-166
-
Journal article (peer-reviewed)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.
|
|
| 2. |
- Andriantiana, Eric Ould Dadah, et al.
(author)
-
Trees with minimum number of infima closed sets
- 2022
-
In: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 345:5
-
Journal article (peer-reviewed)abstract
- Let T be a rooted tree, and V(T) its set of vertices. A subset X of V(T) is called an infima closed set of T if for any two vertices u, v is an element of X, the first common ancestor of u and v is also in X. This paper determines the trees with minimum number of infima closed sets among all rooted trees of given order, thereby answering a question of Klazar. It is shown that these trees are essentially complete binary trees, with the exception of vertices at the last levels. Moreover, an asymptotic estimate for the minimum number of infima closed sets in a tree with n vertices is also provided.
|
|
| 3. |
- Björklund, Johan, et al.
(author)
-
Counterexamples to a monotonicity conjecture for the threshold pebbling number
- 2012
-
In: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:15, s. 2401-2405
-
Journal article (peer-reviewed)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)).
|
|
| 4. |
- Dadedzi, Kenneth, et al.
(author)
-
On the distribution of eigenvalues of increasing trees
- 2024
-
In: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 347:2
-
Journal article (peer-reviewed)abstract
- We prove that the multiplicity of a fixed eigenvalue alpha in a random recursive tree on n vertices satisfies a central limit theorem with mean and variance asymptotically equal to mu alpha n and sigma alpha 2n respectively. It is also shown that mu alpha and sigma alpha 2 are positive for every totally real algebraic integer. The proofs are based on a general result on additive tree functionals due to Holmgren and Janson. In the case of the eigenvalue 0, the constants mu 0 and sigma 02 can be determined explicitly by means of generating functions. Analogous results are also obtained for Laplacian eigenvalues and binary increasing trees.
|
|
| 5. |
- Hammarhjelm, Gustav
(author)
-
The density and minimal gap of visible points in some planar quasicrystals
- 2022
-
In: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 345:12, s. 113074-
-
Journal article (peer-reviewed)abstract
- It has previously been observed that the limiting gap distribution of the directions to visible points of planar quasicrystals may vanish near zero, that is, there exist planar quasicrystals with a positive limiting minimal normalised gap between the angles of visible points. The exact values of these limiting minimal normalised gaps have not been determined. In this paper we give explicit formulas for the densities of visible points for planar quasicrystals from several families, which include the Ammann–Beenker point set and the vertex sets of some rhombic Penrose tilings. Combining these results with a known characterisation of the limiting minimal gap in terms of a probability measure on an associated homogeneous space of quasicrystals, we give explicit values of the limiting minimal normalised gap between the angles of visible points for several families of planar quasicrystals, in particular, for the Ammann–Beenker point set and for the vertex sets of some rhombic Penrose tilings. We also compare our results with numerical observations.
|
|
| 6. |
- Herrmann, Sven, et al.
(author)
-
Optimal realizations of two-dimensional, totally-decomposable metrics
- 2015
-
In: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 338:8, s. 1289-1299
-
Journal article (peer-reviewed)abstract
- A realization of a metric d on a finite set X is a weighted graph (G, w) whose vertex set contains X such that the shortest-path distance between elements of X considered as vertices in G is equal to d. Such a realization (G, w) is called optimal if the sum of its edge weights is minimal over all such realizations. Optimal realizations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. A. Dress (1984) showed that the optimal realizations of a metric dare closely related to a certain polytopal complex that can be canonically associated to d called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of d must always contain an optimal realization as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally-decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realizations of two-dimensional totally-decomposable metrics. (C) 2015 Elsevier B.V. All rights reserved.
|
|
| 7. |
- Janson, Svante, 1955-
(author)
-
A graphon counter example
- 2020
-
In: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:6
-
Journal article (peer-reviewed)abstract
- We give an example of a graphon such that there is no equivalent graphon with a degree function that is (weakly) increasing.
|
|
| 8. |
- Koolen, Jack H., et al.
(author)
-
Injective optimal realizations of finite metric spaces
- 2012
-
In: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:10, s. 1602-1610
-
Journal article (peer-reviewed)abstract
- A realization of a finite metric space (X, d) is a weighted graph (G, w) whose vertex set contains X such that the distances between the elements of X in G correspond to those given by d. Such a realization is called optimal if it has minimal total edge weight. Optimal realizations have applications in fields such as phylogenetics, psychology, compression software and Internet tomography. Given an optimal realization (G, w) of (X, d), there always exist certain "proper" maps from the vertex set of G into the so-called tight span of d. In [A. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. Math. 53 (1984) 321-402], Dress conjectured that any such map must be injective. Although this conjecture was recently disproven, in this paper we show that it is possible to characterize those optimal realizations (G, w) for which certain generalizations of proper maps - that map the geometric realization of (G, w) into the tight span instead of its vertex set - must always be injective. We also prove that these "injective" optimal realizations always exist, and show how they may be constructed from non-injective ones. Ultimately it is hoped that these results will contribute towards developing new ways to compute optimal realizations from tight spans.
|
|
| 9. |
|
|
