Department of Mathematics

Combinatorics and Graph Theory

  •  Ira Gessel, Brandeis University
  •  Counting graphs with neighborhood restrictions
  •  03/31/2021
  •  3:00 PM - 3:50 PM
  •  Online (virtual meeting) (Virtual Meeting Link)
  •  Bruce E Sagan (

A graph is called point-determining (or mating type) if no two vertices have the same neighborhood. An arbitrary graph can be reduced to a point-determining graph by contracting each set of vertices with the same neighborhood to a single vertex, and this decomposition enables us to give a simple exponential generating function for counting point-determining graphs, as accomplished by Ronald Read in 1989. In this talk we will discuss a closely related problem: counting graphs in which no two vertices have complementary neighborhoods. The decomposition approach does not work here. Instead we apply inclusion-exclusion, similarly to its use in rook theory, to obtain a simple exponential generating function for these graphs. We also discuss how this application of inclusion-exclusion is related to Möbius inversion, and how it can be applied to some related problems.



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science