Computation of Graph Polynomials via Tree Decomposition: Theory, Algorithms, and Python Implementation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908560316694528 |
|---|---|
| author | Bafna, Mehul Amirian, Shaghik |
| author_facet | Bafna, Mehul Amirian, Shaghik |
| contents | Graph polynomials encode fundamental combinatorial invariants of graphs. Their computation is investigated using tree and path decomposition frameworks, with formal definitions of treewidth, k-trees, and pathwidth establishing the structural basis for algorithmic efficiency. Explicit algorithms are constructed for each polynomial, leveraging decomposition order and state transformation mappings to enable tractable computation on graphs of bounded treewidth. Python implementations validate the methods, and computational complexity is analyzed with respect to sparse and k-degenerate graph classes. These results advance decomposition-based approaches for polynomial computation in algebraic graph theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16816 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computation of Graph Polynomials via Tree Decomposition: Theory, Algorithms, and Python Implementation Bafna, Mehul Amirian, Shaghik Discrete Mathematics Combinatorics Graph polynomials encode fundamental combinatorial invariants of graphs. Their computation is investigated using tree and path decomposition frameworks, with formal definitions of treewidth, k-trees, and pathwidth establishing the structural basis for algorithmic efficiency. Explicit algorithms are constructed for each polynomial, leveraging decomposition order and state transformation mappings to enable tractable computation on graphs of bounded treewidth. Python implementations validate the methods, and computational complexity is analyzed with respect to sparse and k-degenerate graph classes. These results advance decomposition-based approaches for polynomial computation in algebraic graph theory. |
| title | Computation of Graph Polynomials via Tree Decomposition: Theory, Algorithms, and Python Implementation |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2509.16816 |