Complexity of Families of Multigraphs

Ove Frank, Termeh Shafie

2012-12-01

Abstract

This article describes families of finite multigraphs with labeled or unlabeled edges and vertices. It shows how size and complexity vary for different types of equivalence classes of graphs defined by ignoring only edge labels or ignoring both edge and vertex labels. Complexity is quantified by the distribution of edge multiplicities, and different complexity measures are discussed. Basic occupancy models for multigraphs are used to illustrate different graph distributions on isomorphism and complexity. The loss of information caused by ignoring edge and vertex labels is quantified by entropy and joint information that provide tools for studying properties of and relations between different graph families.

In 2012 JSM Proceedings: Papers Presented at the Joint Statistical Meetings, San Diego, California, July 28-August 2, 2012, and Other ASA-sponsored Conferences, American Statistical Association, 2012