Atlas Mathematical Conference Abstracts || Conferences | Abstracts | for Organizers | About AMCA

Horizons in Combinatorics/16th Shanks Lecture Series
May 21-24, 2001
Vanderbilt University
Nashville, TN, USA

Organizers
Paul Edelman, Mark Ellingham, Jonathan Farley, Mike Plummer, Jerry Spinrad

View Abstracts
Conference Homepage

On Optimal Acyclic Orientations of a Unicyclic Graph
by
Suk Jai Seo
Computer Science Department, University of Alabama in Huntsville
Coauthors: Ashok T. Amin(University of Alabama in Huntsville)

Let (G, R) denote the digraph obtained from graph G by an acyclic orientation R of its edges. By \eta(G, R) we denote the number of pairs of non-adjacent vertices i, j in G such that there exists a directed path either from i to j or from j to i in (G, R). We study orientations of G which maximize \eta(G, R). Such an orientation is referred to as an optimal orientation. Optimum orientations of trees are known. An algorithm is presented to determine an optimal orientation for a unicylic graph.

Date received: April 18, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cags-33.