Rigidity and reconstruction for graphs

Gunther Cornelissen; Janne Kool

doi:10.4171/jfg/76

Rigidity and reconstruction for graphs

Gunther Cornelissen
, Janne Kool

Max Planck Institute. Mathematics

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

The edge reconstruction conjecture of Harary (1964) states
that a finite graph G can be reconstructed up to isomorphism from
the multiset of its edge-deleted subgraphs G − e (with e running over
the edges of G). We put this conjecture in the framework of measuretheoretic rigidity, revealing the importance of the lengths of labeled
closed walks for the problem

Original language	English
Pages (from-to)	247-262
Number of pages	16
Journal	Journal of Fractal Geometry
Volume	6
Issue number	3
DOIs	https://doi.org/10.4171/jfg/76
Publication status	Published - 24 Jun 2019

Keywords

Graph
walks
boundary
Reconstruction conjecture

Access to Document

10.4171/jfg/76

Graph-Boundary-NEWAccepted author manuscript, 308 KBLicence: CC BY

Cite this

@article{8ed9348929c049efaa39997101be1b3c,

title = "Rigidity and reconstruction for graphs",

abstract = "The edge reconstruction conjecture of Harary (1964) states that a finite graph G can be reconstructed up to isomorphism from the multiset of its edge-deleted subgraphs G − e (with e running over the edges of G). We put this conjecture in the framework of measuretheoretic rigidity, revealing the importance of the lengths of labeled closed walks for the problem",

keywords = "Graph, walks, boundary, Reconstruction conjecture",

author = "Gunther Cornelissen and Janne Kool",

year = "2019",

month = jun,

day = "24",

doi = "10.4171/jfg/76",

language = "English",

volume = "6",

pages = "247--262",

journal = "Journal of Fractal Geometry",

issn = "2308-1309",

publisher = "European Mathematical Society Publishing House",

number = "3",

}

TY - JOUR

T1 - Rigidity and reconstruction for graphs

AU - Cornelissen, Gunther

AU - Kool, Janne

PY - 2019/6/24

Y1 - 2019/6/24

N2 - The edge reconstruction conjecture of Harary (1964) states that a finite graph G can be reconstructed up to isomorphism from the multiset of its edge-deleted subgraphs G − e (with e running over the edges of G). We put this conjecture in the framework of measuretheoretic rigidity, revealing the importance of the lengths of labeled closed walks for the problem

AB - The edge reconstruction conjecture of Harary (1964) states that a finite graph G can be reconstructed up to isomorphism from the multiset of its edge-deleted subgraphs G − e (with e running over the edges of G). We put this conjecture in the framework of measuretheoretic rigidity, revealing the importance of the lengths of labeled closed walks for the problem

KW - Graph

KW - walks

KW - boundary

KW - Reconstruction conjecture

U2 - 10.4171/jfg/76

DO - 10.4171/jfg/76

M3 - Article

SN - 2308-1309

VL - 6

SP - 247

EP - 262

JO - Journal of Fractal Geometry

JF - Journal of Fractal Geometry

IS - 3

ER -

Rigidity and reconstruction for graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this