{"ID":2878205,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.19189","arxiv_id":"2508.19189","title":"Reconstructing graphs and their connectivity using graphlets","abstract":"Graphlets are subgraphs rooted at a fixed vertex. The number of occurrences of graphlets aligned to a particular vertex, called graphlet degree sequence (gds), gives a topological description of the surrounding of the analyzed vertex. Graphlet degree distribution (gdd) of a graph is a matrix containing graphlet degree sequence for all vertices in the given graph. A long standing open problem called reconstruction conjecture (RC) asks whether the structure of a graph is uniquely determined by the multiset of its vertex-deleted subgraphs. Graphlet degree distribution up to size (n - 1), (\u003c= n - 1)-gdd, gives more information to reconstruct the graph and we use it to reconstruct any graph having a unique almost-asymmetric vertex-deleted subgraph, where almost-asymmetric means that at most one automorphism orbit has size larger than one. Moreover, we prove that any graph containing a vertex-cut of size 1 or any graph of order n having a vertex with degree at most 2 or at least n-2 is reconstructible from its (\u003c= n - 1)-gdd, which expands results shown in the standard RC. We also discuss the relation between gdd and graph connectivity and the conditions on (\u003c= 3)-gdd, whose breaking means that no graph with such gdd exists.","short_abstract":"Graphlets are subgraphs rooted at a fixed vertex. The number of occurrences of graphlets aligned to a particular vertex, called graphlet degree sequence (gds), gives a topological description of the surrounding of the analyzed vertex. Graphlet degree distribution (gdd) of a graph is a matrix containing graphlet degree...","url_abs":"https://arxiv.org/abs/2508.19189","url_pdf":"https://arxiv.org/pdf/2508.19189v2","authors":"[\"David Hartman\",\"Aneta Pokorná\",\"Daniel Trlifaj\",\"Lluís Vena\"]","published":"2025-08-26T16:51:29Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.SI\"]","methods":"[]","has_code":false}