Edge-Reconstruction of Cartesian Product Graphs

Marcin Jacek Wardynski

Research output: ThesisDoctoral Thesis

44 Downloads (Pure)

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.
Translated title of the contributionKantenrekonstruktion von Kartesischen Produkten von Graphen
Original languageEnglish
QualificationDr.mont.
Awarding Institution
  • Montanuniversität
Supervisors/Advisors
  • Imrich, Wilfried, Assessor A (internal)
  • Aurenhammer, Franz, Assessor B (external), External person
Publication statusPublished - 2020

Bibliographical note

no embargo

Keywords

  • Edge-reconstruction
  • Cartesian product
  • graph algorithms

Cite this