Quantcast

The size of a graph is reconstructible from any n−2n−2 cards

Research paper by PaulBrown, TrevorFenner

Indexed on: 09 Nov '17Published on: 01 Jan '18Published in: Discrete Mathematics



Abstract

Let G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math> be graphs of order n<math class="math"><mi is="true">n</mi></math>. The number of common cards of G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math> is the maximum number of disjoint pairs (v,w)<math class="math"><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">,</mo><mspace width="0.16667em" is="true"></mspace><mi is="true">w</mi><mo is="true">)</mo></mrow></math>, where v<math class="math"><mi is="true">v</mi></math> and w<math class="math"><mi is="true">w</mi></math> are vertices of G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math>, respectively, such that G−v≅H−w<math class="math"><mi is="true">G</mi><mo is="true">−</mo><mi is="true">v</mi><mo is="true">≅</mo><mi is="true">H</mi><mo is="true">−</mo><mi is="true">w</mi></math>. We prove that if the number of common cards of G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math> is at least n−2<math class="math"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">2</mn></math> then G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math> must have the same number of edges when n≥29<math class="math"><mi is="true">n</mi><mo is="true">≥</mo><mn is="true">29</mn></math>. This is the first improvement on the 25<math class="math"><mn is="true">25</mn></math>-year-old result of Myrvold that if G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math> have at least n−1<math class="math"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">1</mn></math> common cards then they have the same number of edges. It also improves on the result of Woodall and others that the numbers of edges of G<math class="math"><mi is="true">G</mi></math> and H<math class="math"><mi is="true">H</mi></math> differ by at most 1<math class="math"><mn is="true">1</mn></math> when they have n−2<math class="math"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">2</mn></math> common cards.