Equitable Graphs and Digraphs
Dr. Grant Zhang
Department of Mathematical Sciences
University of Alabama in Huntsville
October 17, 2003
202 Madison Hall
3:00 PM (Coffee and Cookies at 2:30)
Abstract
Let G be a connected graph with at least two vertices. A probability assignment of G is a function f : E G → 0 1 , where E G is the set of edges in G. For a given probability assignment, the probability of an edge u vin G is f u v , and the probability of a vertex v in G is
p v x x N v f x v
where N v is the set of vertices in G adjacent to v. A probability assignment is said to be equitable if
- p v 1 for every v G .
- the subgraph of G obtained by deleting all edges with probability 0 remains connected.
A graph G is equitable if G contains an equitable probability assignment. Equitable digraphs (directed graphs) are similarly defined. A (1, 2)-factor in G is a spanning subgraph H in G such that the degree of every vertex in H is either 1 or 2. In this talk, we will characterize equitable graphs and digraphs. It turns out that equitable graphs are directly related to the characterization of graphs containing (1, 2)-factors by Tutte in 1953; and equitable digraphs are equivalent to inseparable, doubly stochastic matrices. This is joint work with Kyle Siegrist and Peter Slater.
- Details
- Hits: 91
