Abstract

In this paper, we determine the computational complexity of recognizing two graph classes, grounded 𝖫-graphs and stabbable grid intersection graphs. An 𝖫-shape is made by joining the bottom end-point of a vertical (|) segment to the left end-point of a horizontal (−) segment. The top end- point of the vertical segment is known as the anchor of the 𝖫-shape. Grounded 𝖫-graphs are the intersection graphs of 𝖫-shapes such that all the 𝖫-shapes’ anchors lie on the same horizontal line. We show that recognizing grounded 𝖫-graphs is 𝖭𝖯-complete. This answers an open question asked by Jelínek & Töpfer (Electron. J. Comb., 2019). Grid intersection graphs are the intersection graphs of axis-parallel line segments in which two vertical (similarly, two horizontal) segments cannot intersect. We say that a (not necessarily axis-parallel) straight line 𝓁 stabs a segment 𝑠, if 𝑠 intersects 𝓁. A graph 𝐺 is a stabbable grid intersection graph (S TAB GIG) if there is a grid intersection representation of 𝐺 in which the same line stabs all its segments. We show that recognizing S TAB GIG graphs is 𝖭𝖯-complete, even on a restricted class of graphs. This answers an open question asked by Chaplick et al. (Order, 2018).

Abstract

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