We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G,φ), i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G,φ) with a cluster graph (Gφ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G[S] coincides with Gφ. The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W[1]-hard when parameterized by the number of colors. Thus, MGR remains W[1]-hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W[1]-hard when parameterized by any graph parameter on Gφ, among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of Gφ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when Gφ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size.

Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that has a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d-regular graphs, for constant values of d. Our approach is based on analyzing a greedy algorithm by using the Differential Equations Method. In this way, we obtain the first known non trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald: “Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs”, SIAM J. on Disc. Math. 28(1), 553-575, 2014.

Abstract. Let [Formula: see text] and [Formula: see text] be randomly chosen subsets of the first [Formula: see text] positive integers of cardinalities [Formula: see text], such that their sumset [Formula: see text] has size [Formula: see text]. We show that asymptotically almost surely [Formula: see text] and [Formula: see text] are almost fully contained in arithmetic progressions [Formula: see text] and [Formula: see text] with the same common difference and cardinalities approximately [Formula: see text]. We also prove a counting theorem for such pairs of sets in arbitrary abelian groups. The results hold for [Formula: see text] and [Formula: see text]. Our main tool is an asymmetric version of the method of hypergraph containers which was recently used by Campos to prove similar results in the special case [Formula: see text].

An $L(h_1, h_2, \ldots, h_l)$-labelling of a graph $G$ is a mapping $\phi: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$, we have $|\phi(u) - \phi(v)| \geq h_i$. The span of $\phi$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $\phi$, and $\lambda_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$-labellings of $G$. In this paper we study $\lambda_{h, 1, \ldots, 1}$ for Cartesian products of graphs, where $(h, 1, \ldots, 1)$ is an $l$-tuple with $l \ge 3$. We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$-th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$. All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\ldots ,q_d}$ satisfies $\lambda_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1$ whenever $q_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d$. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.

We shall define the k-isoperimetric connectivity $\lambda _k$ of a regular graph $\Gamma $ as the minimum number of arcs originating in a set with cardinality not exceeding half the order of the graph and containing at least k vertices. Clearly $\lambda _k \leq dk-e_k$, where d is the degree of $\Gamma$ and $e_k$ is the maximal number of edges induced on a set of k vertices. We shall show that Cayley graphs with a prime order and arc-transitive graphs have $\lambda _k =dk-e_k$, provided that $d\geq 3k-3$. We describe all vertex-transitive graphs where $\lambda _2\leq 2d-3$.

A construction of Cayley digraphs associated to arc-colored regular digraphs is presented. The resulting Cayley digraphs, which we call Cayley regular covers, can be seen as a symmetrization of the original digraph. This construction is applied to the de Bruijn digraphs. By using the fact that they are iterated line digraphs of complete symmetric digraphs, valuable information about their Cayley regular covers regarding routings, diameter, hamiltonicity, fault-tolerance properties and degree of symmetry is obtained. In particular, a shortest-path, self-routing algorithm is given for a family of Cayley digraphs which includes the well known butterfly network. These results can be applied to the design of permutation networks. The Cayley regular covers represent sets of permutations in the original digraph which can be performed without conflict. In particular, a sharply 2-transitive group of permutations on the de Bruijn network is presented which admits a simple shortest-path self-routing algorithm. By using the same construction, a Cayley digraph on the symmetric group on the nodes of the de Bruijn digraph of degree two is obtained. The techniques introduced in this paper can also be extended to other families of iterated line digraphs.

Abstract In this paper we consider polygonizations that are robust when faced with changes in the vertices that are present or in their position. We analyze the dynamic maintenance of different types of polygonizations (monotone, star‐shaped…) and we introduce monotone half‐convex polygonizations that are specially interesting because they provide minimum cost per insertion or deletion. If we had to delete not only one point but several external layers of the set, then the onion polygonizations would be suited, because they can be updated in constant time. We also consider the case of points that can be moved to contiguous positions and we show how to polygonize the set for updating in linear time. We deal too with security problems for a polygon: What is the maximum distance the vertices of a polygon could be moved away of their position in such a way that the topology on the boundary of the polygon (or its convexity) remains the same?.