JIPAM logo: Home Link
 
Home Editors Submissions Reviews Volumes RGMIA About Us
 

   
  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.

         
       
  Download Screen PDF
  Download Print PDF
  Send this article to a friend
  Print this page
 

      search [advanced search] copyright 2003 terms and conditions login