LAWCG 2026 - Detailed program

We say that a graph G is an extension of another graph H whenever N_G(x) ≊ H for every x ∈ G, i.e. when the subgraph induced by the open neighborhood of any vertex of G is isomorphic to H. For example, the octahedron is an extension of the 4-cycle and the icosahedron is an extension of the 5-cycle. It is easy to verify that the 3-path does not have any extension.

The finite extension problem (FEP, also known as the Trahtenbrot-Zykov problem) consists in deciding whether a given finite graph H has a finite extension. It is not known whether the FEP is algorithmically decidable, but several closely related problems are known to be undecidable, namely: the infinite extension problem (G must be infinite), the extension problem (G can be either finite or infinite), the mixed finite extension problem (neighborhoods are required to be isomorphic to some H_i in a given finite set of finite graphs ℋ = {H₁, H₂, ..., H_r}) and the 2-mixed finite extension problem (as before but with |ℋ| = r = 2). All these results where obtained by V. K. Bulitko.

In this talk we shall present a procedure (we do not know whether it terminates on all inputs) that do find extensions of graphs for small enough graphs. For instance, it is capable of finding an extension of the icosahedron of order 40 (the icosahedron has exactly 3 extensions of orders 40, 60 and 120). The procedure uses quite a range of algorithmic techniques including: backtracking, branch and bound, priority queues, dynamic programming, simplex method, isomorphism reduction, symmetry exploitation, and (exact) heuristic methods.

All the programming was done in GAP (gap-system.org) plus YAGS (xamanek.izt.uam.mx/yags). This is a joint work with R. Villarroel-Flores and N. García-Colín.

There are different ways of determining whether a (di)graph H is contained in a (di)graph G. We may look for an exact copy of H in G, that is, check whether G contains a sub(di)graph isomorphic to H. However, we may also ask whether G contains a graph "similar to" H, or one that can be obtained from H. The meanings of "similar" or "obtained from" may vary. In this work, we address different relations of this kind, involving (strong and weak) immersions and subdivisions. We refer to them as containment relations or (di)graph morphisms.

The study of these containment relations plays a fundamental role in graph theory, since many interesting classes are defined by forbidding certain (induced) subgraphs. From a computational complexity perspective, for undirected graphs, the problem of determining whether H is "contained" in G is usually polynomial-time solvable. However, this is not always the case when H and G are digraphs.

We investigate the complexity of checking the containment relations in different digraphs, as well as a variant of the problem with parity conditions.