The poset of graphs ordered by induced containment
Smith, Jason P. (2019) The poset of graphs ordered by induced containment. Journal of Combinatorial Theory. Series A, 168. pp. 348-373. ISSN 0097-3165 (https://doi.org/10.1016/j.jcta.2019.06.009)
Preview |
Text.
Filename: Smith_JCT_2019_The_poset_of_graphs_ordered_by_induced_containment.pdf
Accepted Author Manuscript License: Download (256kB)| Preview |
Abstract
We study the poset G of all unlabelled graphs with H≤G if H occurs as an induced subgraph in G. We present some general results on the Möbius function of intervals of G and some results for specific classes of graphs. This includes a case where the Möbius function is given by the Catalan numbers, which we prove using discrete Morse theory, and another case where it equals the Fibonacci numbers, therefore showing that the Möbius function is unbounded. A classification of the disconnected intervals of G is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of G.
-
-
Item type: Article ID code: 69039 Dates: DateEvent30 November 2019Published4 July 2019Published Online25 June 2019AcceptedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 25 Jul 2019 14:35 Last modified: 16 Jul 2024 01:30 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/69039