# Equitable Graphs and Digraphs

## Dr. Grant Zhang

### Department of Mathematical SciencesUniversity of Alabama in Huntsville

October 17, 2003

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

1. p v 1 for every v G .
2. 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.