Abstract. Modular decomposition focuses on repeatedly identifying a module [Formula: see text] (a collection of vertices that shares exactly the same neighborhood outside of [Formula: see text]) and collapsing it into a single vertex. This notion of exactitude of neighborhood is very strict, especially when dealing with real-world graphs. We study new ways to relax this exactitude condition. However, generalizing modular decomposition is far from obvious. Most of the previous proposals lose algebraic properties of modules and thus most of the nice algorithmic consequences. We introduce the notion of an [Formula: see text]- module, a relaxation that maintains some of the algebraic structure. It leads to a new combinatorial decomposition with interesting properties. Among the main results in this work, we show that minimal [Formula: see text]-modules can be computed in polynomial time, and we generalize series and parallel operation between graphs. This leads to [Formula: see text]-cographs which have interesting properties. We study how to generalize Gallai’s theorem corresponding to the case for [Formula: see text], but unfortunately we give evidence that computing such a decomposition tree can be difficult.

A broadcast on a graph G=(V,E) is a function f:V⟶{0,…,diam(G)} such that f(v)≤eG(v) for every vertex v∈V, where diam(G) denotes the diameter of G and eG(v) the eccentricity of v in G. The cost of such a broadcast is then the value ∑v∈Vf(v). Various types of broadcast functions on graphs have been considered in the literature, in relation with domination, irredundance, independence or packing, leading to the introduction of several broadcast numbers on graphs. In this paper, we determine these broadcast numbers for all paths and cycles, thus answering a question raised in Ahmadi et al. (2015).

A distinguishing r-vertex-labelling (resp. r-edge-labelling) of an undirected graph G is a mapping λ from the set of vertices (resp. the set of edges) of G to the set of labels {1,…,r} such that no non-trivial automorphism of G preserves all the vertex (resp. edge) labels. The distinguishing number D(G) and the distinguishing index D′(G) of G are then the smallest r for which G admits a distinguishing r-vertex-labelling or r-edge-labelling, respectively. The distinguishing chromatic number Dχ(G) and the distinguishing chromatic index Dχ′(G) are defined similarly, with the additional requirement that the corresponding labelling must be a proper colouring. These notions readily extend to oriented graphs, by considering arcs instead of edges. In this paper, we study the four corresponding parameters for oriented graphs whose underlying graph is a path, a cycle, a complete graph or a bipartite complete graph. In each case, we determine their minimum and maximum values, taken over all possible orientations of the corresponding underlying graph, except for the minimum values for unbalanced complete bipartite graphs Km,n with m=2, 3 or 4 and n>3, 6 or 13, respectively, or m≥5 and n>2m−m2, for which we only provide upper bounds.

Graph relabeling systems (GRS's) have been introduced as a suitable tool for coding and proving sequential or distributed algorithms on graphs or networks. These systems do not change the underlying structure of the graph on which they work, but only the labeling of its components (edges or vertices). Each relabeling step is fully determined by the knowledge of a fixed size subgraph, the relabeled occurrence. We introduce an extension of that model, the so-called expanding graph relabeling systems (e-GRS's), which allows the generation of sets of graphs by means of component relabeling. We study the generating power of these systems and prove that they enable us to generate any recursively enumerable set of graphs. We first show how the “from left to right” natural orientation of a string-graph, that is a graph representation of a string, can be translated by means of vertex labels in such a way that any local transformation of the string can be simulated by a local relabeling of the string-graph vertices. Using this translation, we show that any phrase-structure string grammar can be simulated by an e-GRS. Finally, we provide a way of encoding graphs as strings and an e-GRS, called the decoder, which can convert any string representation of the encoding of a graph into the graph itself.