 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 15 no. 3
1. 1-local 33/24-competitive Algorithm for Multicoloring Hexagonal Graphs
In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by assigned frequencies, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where each vertex knows its position in the graph. We present a 1-local 33/24-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 7/5-competitive algorithm.
Section:
Graph Theory
2. The Magnus-Derek game in groups
The Magnus-Derek game (also called the maximal variant of the vector game), introduced by Nedev and Muthukrishnan is the following: a token is moved around a table with n positions. In each round of the game Magnus chooses a number and then Derek chooses a direction (clockwise or counterclockwise), and the token moves that many positions into that direction. The goal of Magnus is to maximize the number of positions visited, the goal of Derek is the opposite. In the minimal variant of the game the goals of the two players are exchanged: Magnus wants to minimize the number of positions visited and Derek wants the opposite. Here we introduce a generalization of these games: the token is moved in a group, Magnus chooses an element of the group and Derek decides if the current position is multiplied or divided by that element.
Section:
Combinatorics
3. Surjective cellular automata far from the Garden of Eden
One of the first and most famous results of cellular automata theory, Moore's Garden-of-Eden theorem has been proven to hold if and only if the underlying group possesses the measure-theoretic properties suggested by von Neumann to be the obstacle to the Banach-Tarski paradox. We show that several other results from the literature, already known to characterize surjective cellular automata in dimension d, hold precisely when the Garden-of-Eden theorem does. We focus in particular on the balancedness theorem, which has been proven by Bartholdi to fail on amenable groups, and we measure the amount of such failure.
Section:
Automata, Logic and Semantics
4. Homomorphisms of planar signed graphs to signed projective cubes
We conjecture that every signed graph of unbalanced girth 2g, whose underlying graph is bipartite and planar, admits a homomorphism to the signed projective cube of dimension 2g1. Our main result is to show that for a given g, this conjecture is equivalent to the corresponding case (k = 2g) of a conjecture of Seymour claiming that every planar k-regular multigraph with no odd edge-cut of less than k edges is k-edge-colorable. To this end, we exhibit several properties of signed projective cubes and establish a folding lemma for planar even signed graphs.
5. On the connectedness and diameter of a geometric Johnson graph
Let P be a set of n points in general position in the plane. A subset I of P is called an island if there exists a convex set C such that I = P \C. In this paper we define the generalized island Johnson graph of P as the graph whose vertex consists of all islands of P of cardinality k, two of which are adjacent if their intersection consists of exactly l elements. We show that for large enough values of n, this graph is connected, and give upper and lower bounds on its diameter.
Section:
Combinatorics
6. Clique cycle transversals in graphs with few P₄'s
A graph is extended P4-laden if each of its induced subgraphs with at most six vertices that contains more than two induced P4's is 2K2,C4-free. A cycle transversal (or feedback vertex set) of a graph G is a subset T ⊆ V (G) such that T ∩ V (C) 6= ∅ for every cycle C of G; if, in addition, T is a clique, then T is a clique cycle transversal (cct). Finding a cct in a graph G is equivalent to partitioning V (G) into subsets C and F such that C induces a complete subgraph and F an acyclic subgraph. This work considers the problem of characterizing extended P4-laden graphs admitting a cct. We characterize such graphs by means of a finite family of forbidden induced subgraphs, and present a linear-time algorithm to recognize them.
Section:
Graph Theory
7. A new characterization and a recognition algorithm of Lucas cubes
Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique convex subgraph of an appropriate Fibonacci cube. This serves as the foundation for a recognition algorithm of Lucas cubes that runs in linear time.
Section:
Graph Theory
8. The Cerný conjecture for automata respecting intervals of a directed graph
The Cerný's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n - 1)2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.
Section:
Automata, Logic and Semantics
9. Two player game variant of the Erdős-Szekeres problem
The classical Erd˝os-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erd˝os-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdös-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations
Section:
Combinatorics
10. On the complexity of distributed BFS in ad hoc networks with non-spontaneous wake-ups
We study time and message complexity of the problem of building a BFS tree by a spontaneously awaken node in ad hoc network. Computation is in synchronous rounds, and messages are sent via point-to-point bi-directional links. Network topology is modeled by a graph. Each node knows only its own id and the id's of its neighbors in the network and no pre-processing is allowed; therefore the solutions to the problem of spanning a BFS tree in this setting must be distributed. We deliver a deterministic distributed solution that trades time for messages, mainly, with time complexity O(D . min(D; n=f(n)) . logD . log n) and with the number of point-to-point messages sent O(n. (min(D; n=f(n))+f(n)) . logD. log n), for any n-node network with diameter D and for any monotonically non-decreasing sub-linear integer function f. Function f in the above formulas come from the threshold value on node degrees used by our algorithms, in the sense that nodes with degree at most f(n) are treated differently that the other nodes. This yields the first BFS-finding deterministic distributed algorithm in ad hoc networks working in time o(n) and with o(n2) message complexity, for some suitable functions f(n) = o(n= log2 n), provided D = o(n= log4 n).
Section:
Distributed Computing and Networking
11. Coloring and Guarding Arrangements
Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $\Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between Ω(logn/loglogn). and O(n√). Similarly, we give bounds on the minimum size of a subset S of the intersections of the lines in A such that every cell is bounded by at least one of the vertices in S. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $\Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $\Hcellzone$ hypergraph.
Section:
Combinatorics
12. The resolving number of a graph Delia
We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be NP-hard, we show that the resolving number can be computed in polynomial time. We then relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. With these relations in hand, we characterize the graphs with resolving number 3 extending other studies that provide characterizations for smaller resolving number.
Section:
Graph Theory