Transcript The Circuit Partition Polynomial and Applications to the

The Circuit Partition
Polynomial and Relation to the
Tutte Polynomial Andrea Austin
The project described was supported by the Vermont Genetics Network
through NIH Grant Number 1 P20 RR16462 from the INBRE program
of the National Center for Research Resources.
[email protected]
Prof. Ellis-Monaghan
1
Eulerian Graph
An Eulerian graph is
a graph whose
vertices are all of
even degree.
2
Loops and Multiple Edges
Loop
A loop is an edge that
connects a vertex to
itself.
A bridge is an edge that
connects two components
of a graph. If removed, the
graph would be
disconnected.
A multiple edge is a pair pf
vertices with more than
one edge joining them.
A multigraph is a graph that
may have multiple edges
and/or loops.
3
Multiple
Edges
Multiple
Edges
Loop
Bridge
Multigraph
Oriented Graph/Digraph
An oriented graph is a
graph in which the
edges are directed.
4
Eulerian Orientation
The orientation of a
graph is called
Eulerian if the indegree at each
vertex is equal to
the out-degree.
A simple graph with Eulerian orientation
5
Eulerian Graph States
An Eulerian Graph State of a graph,
G, is the result of replacing all 2nvalent vertices, v, of G, with n 2valent vertices joining pairs of
edges originally adjacent to v.
6
Eulerian k-Partitions
An Eulerian k-Partition is a graph state with k
components.
Example: Consider the Eulerian
3-Partition:
7
Circuit Partition Polynomial

The circuit partition polynomial, j (G; x) , of a
directed
Eulerian
graph, G, is given by


j (G; x)   f k (G ) x k
where f k (G) is the
k 0
number of Eulerian graph states of G with k
components.

The polynomial j (G; x) is given recursively by:
=
+
= x
8
Medial Graph
A medial graph of a connected planar graph,
G, is constructed by putting a vertex on each
edge of G, and drawing edges around the
faces of G.
G
9
Circuit Partition Example
G

Gm
 

j  Gm ; x   x 3  4 x 2  3x


10
Eulerian Graph States
1-component states
X3
3-component state
11
2-component states
X3
Tutte Polynomial
Tutte polynomial for graphs satisfying the following relations:

G has no edges
T (G; x, y)  1

G has an edge e that is neither a loop nor a bridge
T (G; x, y)  (T (G / e; x, y))  T (G  e; x, y)

G is made up of i bridges and j loops
T (G; x, y)  xi y j
12
Tutte Polynomial Example
+
+
e
G
13
Delete e
Contract e
Example…
+
x2
e
+
We delete edge e
and are left with a
bridge, or x.
e
We contract on
edge e and are left
with a loop, or y.
Thus, the Tutte polynomial representation of G is:
T (G; x, y )  x 2  x  y
T (G; x, x)  x 2  2 x
14
Circuit Partition and Tutte

Tutte  Eulerian circuits

If G is a planar graph and Gm is the oriented
medial graph then the Tutte polynomial
encodes information about the numbers of
Euler circuits in Gm

Use the formula:
j(Gm ; x)  xc(G)T (G; x 1, x 1)
Martin, Las Vergnas
15
Circuit Partition vs. Tutte
A Planar graph G
Gm with the vertex
faces colored red
Orient Gm so that red
faces are to the left of
each edge.
  
j Gm ; x   xT G; x  1, x  1  x1[(x  1) 2  2( x  1)]  x 3  4 x 2  3x


16
Recursive Formulas:
Recall: Circuit Partition
Polynomial Recursive Formula
=
+
= x
Tutte Polynomial Recursive
Formula
=
+
delete
=1
17
contract
Circuit Partition-Tutte Connection
Connection via the medial graph:
e
=
+
delete
18
contract
Sources
Ellis-Monaghan, Joanna. Exploring the Tutte-Martin connection, Discrete Mathematics, 281, no
1-3 (2004) 173-187.
Ellis-Monaghan, Joanna. Generalized transition polynomials (with I. Sarmiento), Congressus
Numerantium 155 (2002) 57-69.
Ellis-Monaghan, Joanna. Identities for the circuit partition polynomials, with applications to the
diagonal Tutte polynomial, Advances in Applied Mathematics, 32 no. 1-2, (2004) 188-197.
Ellis-Monaghan, Joanna. Martin polynomial miscellanea. Congressus Numerantium 137
(1999), 19–31.
Ellis-Monaghan, Joanna. New results for the Martin polynomial. Journal of Combinatorial
Theory, series B 74 (1998), 326–52.
M. Las Vergnas, On Eulerian partitions of graphs, Graph Theory and Combinatorics,
Proceedings of Conference, Open University, Milton Keynes, 1978, Research Notes in
Mathematics, Vol. 34, Pitman,Boston, MA, London, 1979, pp. 62–75.
M. Las Vergnas, On the evaluation at (3,3) of the Tutte polynomial of a graph, J. Combin.
Theory,Ser. B 44 (1988) 367–372.
P. Martin, Enumerations euleriennes dans le multigraphs et invariants de Tutte Grothendieck,
Thesis, Grenoble, 1977.
P. Martin, Remarkable valuation of the dichromatic polynomial of planar multigraphs, J.
Combin.Theory, Ser. B 24 (1978) 318–324.
19