Edge-Reconstruction of Cartesian Product Graphs
Research output: Thesis › Doctoral Thesis
Authors
Organisational units
Abstract
This thesis solves the weak edge-reconstruction problem for Cartesian products. In other words, it is shown that any nontrivial finite or infinite Cartesian product G with edge-set E(G) is uniquely determined up to isomorphisms by any edge-deleted subgraph {G − e|e ∈ E(G)}. For finite Cartesian products the thesis also presents an algorithm for the computation of G from G − e in O(m∆²) time, where m is the size of G and ∆ its maximal degree. It improves the straightforward algorithm for reconstruction of G, which has complexity O(mn²), where n is the order of G. Because ∆ can be much smaller than n, the improvement can be substantial.
Details
Translated title of the contribution | Kantenrekonstruktion von Kartesischen Produkten von Graphen |
---|---|
Original language | English |
Qualification | Dr.mont. |
Awarding Institution | |
Supervisors/Advisors |
|
Publication status | Published - 2020 |