Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 3

### Not all simple looking degree sequence problems are easy

Pages: 553 – 566

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n3.a7

#### Authors

#### Abstract

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.

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