A Characterization of Lattice-ordered Graphs
David Leach, Walsh, M. · Zenodo (CERN European Organization for Nuclear Research) · 2006
A finite simple graph G is said to be lattice-ordered if the poset of unlabeled induced subgraphs of G, ordered by inclusion, is lattice-ordered. In this paper, we prove that a graph is lattice-ordered if and only if it or its complement is complete multipartite. Furthermore, if two lattice-ordered graphs have isomorphic unlabeled induced subgraph lattices, then one can be obtained from the other via conjugations and complementations.