2018/10/05 by Andrew Steane, Steane, Andrew M.
Computer Science · Engineering · #Algorithms and Data Compression #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Machine Learning and Algorithms #Medical Image Segmentation Techniques #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1810.02602
openalex publication_date 2018/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many degree sequences can only be realised in graphs that contain a\n`ds-completable card', defined as a vertex-deleted subgraph in which the\nerstwhile neighbours of the deleted vertex can be identified from their\ndegrees, if one knows the degree sequence of the original graph. We obtain\nconditions on the degree sequence, such that graphs whose degree sequence\nsatisfies one of the conditions must contain such a card. The methods allow all\nsuch sequences on graphs of order up to 10 to be identified, and some fraction\nof the sequences for larger graphs. Among other applications, this can be used\nto reduce the computational task of generating graphs of a given degree\nsequence without duplicates.\n