View Calendar

Q Club - On Counting Triangles

Valentine Hall
3/25/14 11:45am to 12:15pm

Please join us on Tuesday, March 25 at 11:50am for our next Q Club! The meeting will be in Valentine 205/206, and Eric Budge and Steve Petramale will be presenting.

Title: On Counting Triangles

Abstract: Algorithms for counting triangles in massive graphs have been studied intensely. This fundamental tool has been utilized in network analysis for the computation of metrics including clustering coefficients and transitivity ratios. The degree sequence S of a graph G is a list of the degrees of the vertices in G in non-increasing order. A particular degree sequence S is called graphic if and only if a graph G can be created using S. This work focuses on graphs with degree sequences containing a unique triple, a sequence which has three repeated terms and all other terms distinct. Polynomial expressions are given which count the number of triangles in realizations of such graphic unique triple sequences.