Recognizing cycles from partial decks

Abstract

The unlabeled subgraphs G-v are called the cards of a graph G and the deck of the graph G is the multiset {G-v: v \in V(G)}. In 1942 Kelly conjectured that any finite, simple, undirected graph on at least 3 vertices is uniquely determined by its deck. Although this conjecture is still open, it is known that many properties can be determined from (sub)decks of G. For example, I proved that every graph G on n vertices has a subdeck of [n/2]+2 cards from which we can determine the number of edges of G.

Wendy Myrvold [Ars Combinatoria, 1989] showed that a disconnected graph and a connected graph both on n vertices have at most [n/2]+1 cards in common. Moreover, she found infinite families of trees and disconnected forests for which this upper bound is attained. Hence, we need at least [n/2]+2 cards to determine whether a graph is a tree. Bowler, Brown, and Fenner [Journal of Graph Theory, 2010] conjectured that this bound is tight. In this thesis, I prove this conjecture for sufficiently large n: I show that a tree T and a unicyclic graph G on n vertices have at most [n/2]+1 common cards.

Based on this theorem, I show that any forest and non-forest also have at most [n/2]+1 common cards. Moreover, I have classified all pairs (except finitely many) for which this bound is strict. Furthermore, I adapted the main ideas of the proof for trees to show that the girth of a graph on $n$ vertices can be determined based on any 2n/3+1 of its cards. Lastly, I showed that any 5n/6+2 cards determine whether a graph is bipartite.