TY - GEN
T1 - Reconstructing Graphs from Connected Triples
AU - Mannens, Isja
AU - Groenland, Carla
AU - Kreveld, Marc van
AU - Bastide, Paul
AU - Cook, Linda
AU - Erickson, Jeff
AU - Vermeulen, Jordi Luca
PY - 2023
Y1 - 2023
N2 - We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different (labelled) graphs may have the same set of connected triples, making unique reconstruction of the original graph from the triples impossible. We identify some families of graphs (including triangle-free graphs) for which all graphs have a different set of connected triples. We also give algorithms that reconstruct a graph from a set of triples, and for testing if this reconstruction is unique. Finally, we study a possible extension of the model in which the subsets of size k that induce a connected graph are given for larger (fixed) values of k.
AB - We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different (labelled) graphs may have the same set of connected triples, making unique reconstruction of the original graph from the triples impossible. We identify some families of graphs (including triangle-free graphs) for which all graphs have a different set of connected triples. We also give algorithms that reconstruct a graph from a set of triples, and for testing if this reconstruction is unique. Finally, we study a possible extension of the model in which the subsets of size k that induce a connected graph are given for larger (fixed) values of k.
U2 - 10.48550/arXiv.2303.06609
DO - 10.48550/arXiv.2303.06609
M3 - Conference contribution
BT - WG 2023, Fribourg, Switzerland, 28/06/23
ER -