Crespelle, Christophe Latapy, Matthieu Phan, Thi Ha Duong

We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iterati...

Jeandel, Emmanuel Rao, Michael

We present a new aperiodic tileset containing 11 Wang tiles on 4 colors, and we show that this tileset is minimal, in the sense that no Wang set with either fewer than 11 tiles or fewer than 4 colors is aperiodic. This gives a definitive answer to the problem raised by Wang in 1961.

Dailly, Antoine Duchene, Eric Larsson, Urban Paris, Gabrielle

Taking-and-breaking games are combinatorial games played on heaps of tokens, where both players are allowed to remove tokens from a heap and/or split a heap into smaller heaps. Subtraction games, octal and hexadecimal games are well-known families of such games. We here consider the set of pure breaking games, that correspond to the family of takin...

Thraves-Caro, Christopher Doncel, Josu Brun, Olivier

In this work we study the Optimal Path Discovery (OPD) problem. That is: given a complete graph G = (V, E), a function F : 2 E → [0, ∞) that assigns a positive value to each sub set of E, two nodes s and t in V , and a positive hidden value f (e) for each edge e ∈ E, discover a path P * between s and t that optimizes the value of F (P *). The issue...

Vallée, Brigitte Cesaratto, Eda

Submitted to a journal

Dorbec, Paul González, Antonio Pennarun, Claire

Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially...

Defrain, Oscar Nourine, Lhouari

We investigate two different approaches to enumerate minimal dominating sets of a graph using structural properties based on neighborhood inclusion. In the first approach, we define a preference relation on a graph G as a poset on the set of vertices of G. In particular, we consider the poset of closed neighborhood inclusion P(G) and define the not...

Dvořák, Zdeněk Hu, Xiaolan Sereni, Jean-Sébastien

In 1980, Erd\H{o}s, Rubin and Taylor asked whether for all positive integers $a$, $b$, and $m$, every $(a:b)$-choosable graph is also $(am:bm)$-choosable. We provide a negative answer by exhibiting a $4$-choosable graph that is not $(8:2)$-choosable.

Bouznif, Marwane Darlay, Julien Moncel, Julien Preissmann, Myriam

In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. The...

Bazin, Alexandre

Implication bases in n-lattices are not formally defined. We clarify the different types of implications we need to reconstruct a concept n-lattice and show they can be derived from the same set of implications. We use this to identify a particular type of implication base in n-contexts. Finally, we provide an algorithm for computing implicational ...