Construction numbers: How to build a graph?
–arXiv.org Artificial Intelligence
Counting the number of linear extensions of a partial order was considered by Stanley about 50 years ago. For the partial order on the vertices and edges of a graph determined by inclusion, we call such linear extensions {\it construction sequences} for the graph as each edge follows both of its endpoints. The number of such sequences for paths, cycles, stars, double-stars, and complete graphs is found. For paths, we agree with Stanley (the Tangent numbers) and get formulas for the other classes. Structure and applications are also studied.
arXiv.org Artificial Intelligence
Oct-2-2023
- Country:
- Genre:
- Research Report (0.50)
- Technology: