Enumeration of Tree-like Multigraphs with a Given Number of Vertices, Self-loops and Multiple Edges
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909870057324544 |
|---|---|
| author | Azam, Naveed Ahmed Hayat, Seemab |
| author_facet | Azam, Naveed Ahmed Hayat, Seemab |
| contents | Counting non-isomorphic tree-like multigraphs that include self-loops and multiple edges is an important problem in combinatorial enumeration, with applications in chemical graph theory, polymer science, and network modeling. Traditional counting techniques, such as Polya's theorem and branching algorithms, often face limitations due to symmetry handling and computational complexity. This study presents a unified dynamic programming framework for enumerating tree-like graphs characterized by a fixed number of vertices, self-loops, and multiple edges. The proposed method utilizes canonical rooted representations and recursive decomposition of subgraphs to eliminate redundant configurations, ensuring exact counting without the need for explicit structure generation. The framework also provides analytical bounds and recurrence relations that describe the growth behaviour of such multigraphs. This work extends previous models that treated self-loops and multiple edges separately, offering a general theoretical foundation for the enumeration of complex tree-like multigraphs in both mathematical and chemical domains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22302 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enumeration of Tree-like Multigraphs with a Given Number of Vertices, Self-loops and Multiple Edges Azam, Naveed Ahmed Hayat, Seemab Discrete Mathematics Combinatorics Counting non-isomorphic tree-like multigraphs that include self-loops and multiple edges is an important problem in combinatorial enumeration, with applications in chemical graph theory, polymer science, and network modeling. Traditional counting techniques, such as Polya's theorem and branching algorithms, often face limitations due to symmetry handling and computational complexity. This study presents a unified dynamic programming framework for enumerating tree-like graphs characterized by a fixed number of vertices, self-loops, and multiple edges. The proposed method utilizes canonical rooted representations and recursive decomposition of subgraphs to eliminate redundant configurations, ensuring exact counting without the need for explicit structure generation. The framework also provides analytical bounds and recurrence relations that describe the growth behaviour of such multigraphs. This work extends previous models that treated self-loops and multiple edges separately, offering a general theoretical foundation for the enumeration of complex tree-like multigraphs in both mathematical and chemical domains. |
| title | Enumeration of Tree-like Multigraphs with a Given Number of Vertices, Self-loops and Multiple Edges |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2510.22302 |