G. Sorkin

most citedA Two-Variable Interlace Polynomial

2 citations · 2 across the 2 of their papers we have counts for

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2007

A tight bound on the collection of edges in MSTs of induced subgraphs

Gregory B. Sorkin, Angelika Steger, Rico Zenklusen

Let $G = (V, E)$ be a complete $n$ -vertex graph with distinct positive edge weights. We prove that for $k \in {1, 2, ..., n - 1}$ , the set consisting of the edges of all minimum spanning t…

math.CO2002★ 2 cited

A Two-Variable Interlace Polynomial

Richard Arratia, Bela Bollobas, Gregory B. Sorkin

We introduce a new graph polynomial in two variables. This ``interlace'' polynomial can be computed in two very different ways. The first is an expansion analogous to the state spa…

math.CO2002

The Interlace Polynomial of a Graph

Richard Arratia, Bela Bollobas, Gregory B. Sorkin

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable ``interlace polynomial'' for any graph. The polynomial satisfies a beautiful and unexpec…