Realization of Temporally Connected Graphs Based on Degree Sequences
This solves a relaxation of a known NP-hard problem, offering efficient algorithms for a fundamental graph realization problem in temporal networks.
The paper characterizes which degree sequences can be realized as temporally connected graphs and provides O(n) and O(n+m) time recognition algorithms for graphical and multigraphical degree sequences, respectively, with constructive outputs.
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., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in $O(n)$ time for graphical degree sequences (realized as simple temporal graphs) and in $O(n+m)$ time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive $O(n+m)$ time algorithm that outputs, for a given (multi)graphical degree sequence $\mathbf{d}$, a temporally connected graph whose underlying (multi)graph is a realization of $\mathbf{d}$, if one exists.