Gajjar, Kshitij

The concept of sum labelling was introduced in 1990 by Harary. A graph is a sum graph if its vertices can be labelled by distinct positive integers in such a way that two vertices are connected by an edge if and only if the sum of their labels is the label of another vertex in the graph. It is easy to see that every sum graph has at least one isolated vertex, and every graph can be made a sum graph by adding at most n2 isolated vertices to it. The minimum number of isolated vertices that need to be added to a graph to make it a sum graph is called the sum number of the graph. The sum number of several prominent graph classes (e.g., cycles, trees, complete graphs) is already well known. We examine the effect of taking the disjoint union of graphs on the sum number. In particular, we provide a complete characterisation of the sum number of graphs of maximum degree two, since every such graph is the disjoint union of paths and cycles.

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming P≠NP), even for relaxed variants of the problem (assuming P≠PSPACE). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most k (for a fixed integer k≥2) contiguous vertices on a shortest path can be changed at a time.

Planar graphs can be represented as the intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin & Gonçalves, SODA 2009), L-shapes (Gonçalves et al., SODA 2018). For general graphs, however, even deciding whether such representations exist is often NP-hard. We consider apex graphs, i.e., graphs that can be made planar by removing one vertex from them. We show, somewhat surprisingly, that deciding whether geometric representations exist for apex graphs is NP-hard as well. More precisely, we show that for every fixed positive integer g and every graph class G such that [Formula presented], it is NP-hard to decide whether an input graph belongs to the graph class G, even when the inputs are restricted to apex graphs of girth g. Here, [Formula presented] is the class of intersection graphs of axis-parallel line segments (where horizontal segments intersect only vertical segments), and [Formula presented] is the class of intersection graphs of simple curves (where two intersecting curves cross each other exactly once) in the plane. This partially answers an open question raised by Kratochvíl & Pergel (COCOON, 2007). Most known reductions for earlier proofs of NP-hardness for these problems are from variants of 3-SAT (mainly PLANAR 3-CONNECTED 3-SAT). We reduce from the [Formula presented] [Formula presented] [Formula presented] problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric intersection graphs.