| |
|
|
| |
Volume 6, Issue 1, Article 2 |
|
|
|
|
|
| |
The Lattice of Threshold Graphs
|
| |
|
Authors: |
Russell Merris, Tom Roby, |
|
| |
|
Keywords:
|
Automorphism group, Distributive lattice, Eigenvalue, Graphic partition, Laplacian spectrum, Order ideal, Poset, Projective representation, Saturated chain, Shifted shape, Split graph, Strict partition, Threshold graph, Young subgroup, Young's lattice. |
|
| |
|
Date Received:
|
31/10/03 |
|
| |
|
Date Accepted:
|
28/10/04 |
|
| |
|
Subject Codes: |
05A17, 05C75.
|
|
| |
|
Editors: |
Roy Mathias, |
|
| |
|
|
|
|
|
| |
|
Abstract: |
Due in part to their many interesting properties, a family of graphs has been studied under a variety of names, by various authors, since the late 1970's. Only recently has it become apparent that the many different looking definitions for these threshold graphs are all equivalent. While the pedigree of strict partitions of positive integers is much older, their evolution into the lattice of shifted shapes is relatively recent. In this partly expository article we show, from the perspective of partially ordered sets, that the family of connected threshold graphs is isomorphic to the lattice of shifted shapes, and then discuss some implications of this identification for threshold graphs.
|
|
|
|
|
|
| |
|
|
|
|
| |
|
|
|
|
|
Home
