2025/08/26 by Hartman, David, Pokorná, Aneta, Trlifaj, Daniel
#05C60 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.2508.19189
Graphlets are small subgraphs rooted at a fixed vertex. The number of occurrences of graphlets aligned to a particular vertex, called graphlet degree sequence, gives a topological description of the surrounding of the analyzed vertex. In this article, we study properties and uniqueness of graphlet degree sequences. The information given by graphlets up to size (n-1) is utilized graphs having certain type of asymmetric vertex-deleted subgraphs. Moreover, we show a reconstruction of trees from their (<= n-1)-graphlet degree sequences, which is much easier compared to the standard reconstruction from vertex-deleted subgraphs.