 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 12 no. 1
1. Deciding whether the ordering is necessary in a Presburger formula
We characterize the relations which are first-order definable in the model of the group of integers with the constant 1. This allows us to show that given a relation defined by a first-order formula in this model enriched with the usual ordering, it is recursively decidable whether or not it is first-order definable without the ordering.
Section:
Automata, Logic and Semantics
2. On the existence of block-transitive combinatorial designs
Block-transitive Steiner t-designs form a central part of the study of highly symmetric combinatorial configurations at the interface of several disciplines, including group theory, geometry, combinatorics, coding and information theory, and cryptography. The main result of the paper settles an important open question: There exist no non-trivial examples with t = 7 (or larger). The proof is based on the classification of the finite 3-homogeneous permutation groups, itself relying on the finite simple group classification.
Section:
Combinatorics
3. Symmetric monochromatic subsets in colorings of the Lobachevsky plane
We prove that for each partition of the Lobachevsky plane into finitely many Borel pieces one of the cells of the partition contains an unbounded centrally symmetric subset.
Section:
Combinatorics
4. Edge-Removal and Non-Crossing Configurations in Geometric Graphs
A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V. We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.
Section:
Graph and Algorithms
5. Generating involutions, derangements, and relatives by ECO
We show how the ECO method can be applied to exhaustively generate some classes of permutations. A previous work initiating this technique and motivating our research was published in Ac ta Informatica, 2004, by S. Bacchelli, E. Barcucci, E. Grazzini and E. Pergola.
Section:
Combinatorics
6. On edge-intersection graphs of k-bend paths in grids
Edge-intersection graphs of paths in grids are graphs that can be represented such that vertices are paths in a grid and edges between vertices of the graph exist whenever two grid paths share a grid edge. This type of graphs is motivated by applications in conflict resolution of paths in grid networks. In this paper, we continue the study of edge-intersection graphs of paths in a grid, which was initiated by Golumbic, Lipshteyn and Stern. We show that for any k, if the number of bends in each path is restricted to be at most k, then not all graphs can be represented. Then we study some graph classes that can be represented with k-bend paths, for small k. We show that every planar graph has a representation with 5-bend paths, every outerplanar graph has a representation with 3-bend paths, and every planar bipartite graph has a representation with 2-bend paths. We also study line graphs, graphs of bounded pathwidth, and graphs with -regular edge orientations.
7. Acyclic colourings of graphs with bounded degree
A k-colouring of a graph G is called acyclic if for every two distinct colours i and j, the subgraph induced in G by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, there are no bichromatic alternating cycles. In 1999 Boiron et al. conjectured that a graph G with maximum degree at most 3 has an acyclic 2-colouring such that the set of vertices in each colour induces a subgraph with maximum degree at most 2. In this paper we prove this conjecture and show that such a colouring of a cubic graph can be determined in polynomial time. We also prove that it is an NP-complete problem to decide if a graph with maximum degree 4 has the above mentioned colouring.
Section:
Graph and Algorithms
8. An improved bound on the largest induced forests for triangle-free planar graphs
We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth.
9. Tight Bounds for Delay-Sensitive Aggregation
This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. We derive an upper bound on the competitive ratio of O(min (h, c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Omega(min (h, c)). For chain networks, we prove a tight competitive ratio of Theta(min (root h, c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.
Section:
Distributed Computing and Networking
10. On a 1, 2 Conjecture
Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary G? We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to C use weights from 1 to 11, as well as from 1 to 11 [chi(G)/2] + 1, for an arbitrary graph G.
Section:
Graph and Algorithms