Abstract
The set of all unlabeled induced subgraphs of a finite graph G can be made into a poset by defining \(H_1 \le H_2\) iff \(H_1\) is a subgraph of \(H_2\). This paper discusses some of the connections between the graph properties of G and the order theoretic properties of this poset. This paper then restricts this class of subgraphs to only connected unlabeled induced subgraphs and looks at some of the order theoretic properties of that poset.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2000)
Jacobson, M.S., Kezdy, A.E., Seif, S.: The poset on connected induced subgraphs need not be Sperner. Order 12(3), 315–318 (1995)
Kezdy, A.E., Seif, S.: When is a poset isomorphic to the poset of connected induced subgraphs of a graph? Southwest J Pure Appl Math 1, 42–50 (1996)
Trotter Jr., W.T., Moore Jr., J.I.: Some theorems on graphs and posets. Discrete Math. 15(1), 79–84 (1976)
Leach, D., Walsh, M.: A characterization of lattice-ordered graphs. In: Combinatorial Number Theory, pp. 327–332 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by W. DeMeo.
Dedicated to Ralph Freese, Bill Lampe, and J.B. Nation.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Sykes, S.R. The poset of unlabeled induced subgraphs of a finite graph. Algebra Univers. 81, 11 (2020). https://doi.org/10.1007/s00012-020-0642-0
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-020-0642-0