**The computational hardness of**.*d*K-series

W. E. Devanny, D. Eppstein, and B. Tilman.

*NetSci2016*poster session, Seoul, Korea.The

*d*K-series is an extension of the degree sequence of a graph to a*d*-dimensional tensor, describing the number of*d*-tuples of vertices with each possible combination of degrees and adjacencies. As we show, it is NP-hard to determine whether such a tensor represents a valid graph, for any*d*≥ 3, or for*d*= 2 if the number of triangles in the graph is also specified (or constrained to be zero).

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.