Vol. 15 no. 3

1. On the connectedness and diameter of a geometric Johnson graph

Bautista-Santiago, Crevel ; Cano, Javier ; Fabila-Monroy, Ruy ; Flores-Peñaloza, David ; González-Aguilar, Hernàn ; Lara, Dolores ; Sarmiento, Eliseo ; Urrutia, Jorge.
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 […]
Section: Combinatorics

2. Clique cycle transversals in graphs with few P₄'s

Bravo, Raquel ; Klein, Sulamita ; Nogueira, Loana Tito ; Protti, Fábio.
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 […]
Section: Graph Theory

3. Homomorphisms of planar signed graphs to signed projective cubes

Naserasr, Reza ; Rollova, Edita ; Sopena, Eric.
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 […]

4. A new characterization and a recognition algorithm of Lucas cubes

Taranenko, Andrej.
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 […]
Section: Graph Theory

5. Surjective cellular automata far from the Garden of Eden

Capobianco, Silvio ; Guillon, Pierre ; Kari, Jarkko.
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 […]
Section: Automata, Logic and Semantics

6. The Cerný conjecture for automata respecting intervals of a directed graph

Grech, Mariusz ; Kisielewicz, Andrzej.
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 […]
Section: Automata, Logic and Semantics

7. Two player game variant of the Erd\H os-Szekeres problem

Kolipaka, Parikshit ; Govindarajan, Sathish.
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 […]
Section: Combinatorics

8. The Magnus-Derek game in groups

Gerbner, Dániel.
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), […]
Section: Combinatorics

9. On the complexity of distributed BFS in ad hoc networks with non-spontaneous wake-ups

Kowalski, Dariusz ; Krzywdziński, Krzysztof.
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 […]
Section: Distributed Computing and Networking

10. 1-local 33/24-competitive Algorithm for Multicoloring Hexagonal Graphs

Witkowski, Rafal ; Žerovnik, Janez.
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 […]
Section: Graph Theory

11. Coloring and Guarding Arrangements

Bose, Prosenjit ; Cardinal, Jean ; Collette, Sébastien ; Hurtado, Ferran ; Korman, Matias ; Langerman, Stefan ; Taslakian, Perouz.
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 […]
Section: Combinatorics

12. The resolving number of a graph Delia

Garijo, Delia ; González, Antonio ; Márquez, Alberto.
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 […]
Section: Graph Theory