TY - BOOK

T1 - Edge-Reconstruction of Cartesian Product Graphs

AU - Wardynski, Marcin Jacek

N1 - no embargo

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Edge-reconstruction

KW - Cartesian product

KW - graph algorithms

KW - Kantenrekonstruktion

KW - Kartesisches Produkt

KW - Graph Algorithmen

M3 - Doctoral Thesis

ER -