We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

math.CO

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Mathematics > Combinatorics

Title: Construction numbers: How to build a graph?

Abstract: 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.
Comments: 17 pages; Problem 12401 - 06 in the June 2023 issue of the American Math Monthly is to find this construction number for $K_n$. Solutions are due by {\bf October 31, 2023}
Subjects: Combinatorics (math.CO); Artificial Intelligence (cs.AI)
MSC classes: 05C30, 05A05, 90B35
Cite as: arXiv:2302.13186 [math.CO]
  (or arXiv:2302.13186v3 [math.CO] for this version)

Submission history

From: Paul Kainen [view email]
[v1] Sat, 25 Feb 2023 22:54:27 GMT (15kb)
[v2] Mon, 29 May 2023 18:36:39 GMT (22kb)
[v3] Mon, 2 Oct 2023 17:51:58 GMT (20kb)

Link back to: arXiv, form interface, contact.