circuit partition polynomial

Download Report

Transcript circuit partition polynomial

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
Orientation & Eulerian Graphs
An oriented graph is a graph in
which the edges are directed.
An Eulerian graph is a graph
whose vertices are all of even
degree.
The orientation of a graph is
called Eulerian if the indegree at each vertex is
equal to the out-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
Eulerian Graph State/k-Partition
An Eulerian Graph State of a graph, G, is the result
of replacing all 2n-valent vertices, v, of G, with n 2valent vertices joining pairs of edges originally
adjacent to v.
An Eulerian k-Partition is a graph state with k
components.
Example: Consider the Eulerian 3-Partition:
4
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
5
Circuit Partition:
Finding the Polynomial Example

Eg. Let G =
There are 6 one component states. There are
also 8 two component states and 2 three
component states. Thus,
j (G; x)  2 x 3  8 x 2  6 x
A one component state
6
A two component state
A three component state
Tutte Polynomial
Tutte polynomial for graphs satisfies 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
7
Tutte Polynomial Example
+
e
G
8
Delete e
Contract e
Example…
+
x2
+
We delete edge e
and are left with a
bridge, or x.
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
9
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
10
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 (G m ; x)  x c (G )T (G; x  1, x  1)
Martin, Las Vergnas
11
Circuit Partition and Tutte
A Planar graph G
Gm with the vertex
faces colored black
Orient Gm so that
black 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


12
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.
13