{"id":"arxiv/2608.11930","url":"https://arxiv.org/abs/2608.11930","tags":["math.CO","cs.DM"],"score":0,"title":"Nonisomorphic Graphs Can Share an Arbitrarily Large Fraction of Their Vertex-Deleted Cards","domain":"math.CO","source":"arxiv","authors":["Sergey Ivanov"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, its vertex deck is the multiset of graphs obtained by deleting one vertex. Bowler, Brown, and Fenner (BBF) proposed $2\\lfloor(n-1)/3\\rfloor$ as the maximum possible overlap between the decks of two nonisomorphic $n$-vertex graphs, for all sufficiently large $n$. We first give an explicit pair of connected nonisomorphic graphs on $78$ vertices with at least $51$ common cards, exceeding BBF's predicted value of $50$. We then construct, for every even $r\\ge4$, families at arbitrarily large orders whose overlap fraction is asymptotically at least $1-1/r$. Consequently, for every…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}