Realization of Temporally Connected Graphs Based on Degree Sequences

Arnaud Casteigts, Michelle Döring, Nils Morawietz

Given an undirected graph $G$, the problem of deciding whether $G$ admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al.…