Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1996, pp. 42–50 Submitted: January 12, 1996. Published: May 28, 1996.

WHEN IS A POSET ISOMORPHIC TO THE POSET OF

CONNECTED INDUCED SUBGRAPHS OF A GRAPH?

André E. Kézdy and Steve Seif

Abstract. Suppose G is a finite connected graph. Let C(G) denote the inclusion ordering on the connected vertex-induced subgraphs of G. Resolving a problem posed by Steve Steinsaltz, we characterize posets that arise in this way. In particular, we show that, for a finite poset P, there exists a finite graph G such that C(G) ≅ P if and only if P is atom-height and properly semimodular. We present a similar characterization for infinite posets.

(1991) A.M.S. Subject Classification Codes. 05.

Key Words and Phrases. Connected graph, poset.

Department of Mathematics, University of Louisville, Louisville, KY 40292. E-mail Address: swseif01@homer.louisville.edu \begin{matrix}c \\ ◯ \end{matrix}1996 Cameron University

Typeset by AMS-TEX