Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2508.19189 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908739576004608 |
|---|---|
| author | Hartman, David Pokorná, Aneta Trlifaj, Daniel Vena, Lluís |
| author_facet | Hartman, David Pokorná, Aneta Trlifaj, Daniel Vena, Lluís |
| contents | 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), (<= 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 (<= 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 (<= 3)-gdd, whose breaking means that no graph with such gdd exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19189 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reconstructing graphs and their connectivity using graphlets Hartman, David Pokorná, Aneta Trlifaj, Daniel Vena, Lluís Combinatorics Discrete Mathematics Social and Information Networks 05C60 G.2.2 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), (<= 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 (<= 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 (<= 3)-gdd, whose breaking means that no graph with such gdd exists. |
| title | Reconstructing graphs and their connectivity using graphlets |
| topic | Combinatorics Discrete Mathematics Social and Information Networks 05C60 G.2.2 |
| url | https://arxiv.org/abs/2508.19189 |