An Efficient Algorithm to Generate all Labeled Triangle-free Graphs with a given Graphical Degree Sequence
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915747465265152 |
|---|---|
| author | Wang, Kai |
| author_facet | Wang, Kai |
| contents | We extend our previous algorithm that generates all labeled graphs with a given graphical degree sequence to generate all labeled triangle-free graphs with a given graphical degree sequence. The algorithm uses various pruning techniques to avoid having to first generate all labeled realizations of the input sequence and then testing whether each labeled realization is triangle-free. It can be further extended to generate all labeled bipartite graphs with a given graphical degree sequence by adding a simple test whether each generated triangle-free realization is a bipartite graph. All output graphs are generated in the lexicographical ordering as in the original algorithm. The algorithms can also be easily parallelized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15943 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Efficient Algorithm to Generate all Labeled Triangle-free Graphs with a given Graphical Degree Sequence Wang, Kai Combinatorics Computational Complexity 05C30 We extend our previous algorithm that generates all labeled graphs with a given graphical degree sequence to generate all labeled triangle-free graphs with a given graphical degree sequence. The algorithm uses various pruning techniques to avoid having to first generate all labeled realizations of the input sequence and then testing whether each labeled realization is triangle-free. It can be further extended to generate all labeled bipartite graphs with a given graphical degree sequence by adding a simple test whether each generated triangle-free realization is a bipartite graph. All output graphs are generated in the lexicographical ordering as in the original algorithm. The algorithms can also be easily parallelized. |
| title | An Efficient Algorithm to Generate all Labeled Triangle-free Graphs with a given Graphical Degree Sequence |
| topic | Combinatorics Computational Complexity 05C30 |
| url | https://arxiv.org/abs/2601.15943 |