Not all simple looking degree sequence problems are easy

Degree sequence (DS) problems have been around for at least one hundred twenty years, and with the advent of network science, more and more complicated and structured DS problems were invented. Interestingly enough all those problems so far are computationally easy. It is clear, however, that we will find soon computationally hard DS problems. In this paper we want to find such hard DS problems with relatively simple definition.

For a vertex $v$ in the simple graph $G$ denote $d_i (v)$ the number of vertices at distance exactly $i$ from $v$. Then $d_1 (v)$ is the usual degree of vertex $v$. The vector $\mathbf{d}^2 (G) = ((d_1 (v_1), d_2 (v_1)), \dotsc , (d_1 (v_n), d_2 (v_n))$ is the second order degree sequence of the graph $G$. In this note we show that the problem to decide whether a sequence of natural numbers $((i_1, j_1), \dotsc (i_n, j_n))$ is a second order degree sequence of a simple undirected graph $G$ is strongly $NP$-complete. Then we will discuss some further $NP$-complete DS problems.

Keywords

degree sequences of simple graphs, second order degree sequences, basket filling problem, neighborhood degree sum

2010 Mathematics Subject Classification

Primary 05C07, 60K35. Secondary 68R05.

Full Text (PDF format)

Both authors were supported partly by National Research, Development and Innovation Office – NKFIH, under the grants K 116769 and SNN 116095.

Received 3 November 2016

Published 18 May 2018