2016/09/01 by Douglas B. West, West, Douglas B., Hannah Spinoza +1 · 1 citation
Computer Science · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1609.00284
openalex publication_date 2016/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The k-deck of a graph is its multiset of induced subgraphs on k vertices. We prove that n-vertex graphs with maximum degree 2 have the same k-decks if each cycle has at least k+1 vertices, each path component has at least k-1 vertices, and the number of edges is the same. Using this for lower bounds, we obtain for each graph with maximum degree at most 2 the least k such that it is determined by its k-deck. For the n-vertex cycle this value is \lfloor n/2 \rfloor, and for the n-vertex path it is \lfloor n/2 \rfloor+1. Also, the least k such that the k-deck of an n-vertex graph always determines whether it is connected is at least \lfloor n/2 \rfloor +1.