COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@csc.uvic.ca). To get email notification of our seminars and other events, you can subscribe to the CAG email list at http://mailman.csc.uvic.ca/mailman/listinfo/cag
Date  Place  Time  Speaker  Abbreviated Title 

Fri. Sept. 9  ECS 660  3:30pm  Stephen T. Hedetniemi  Classifying Graphs by Degrees 
Fri. Oct. 21  MAC D101  2:30pm  Joergen BangJensen  Antistrong Digraphs 
An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that one can decide in linear time whether they are connected by an antidirected trail. A digraph D is antistrong if it contains an antidirected (x, y)trail starting and ending with a forward arc for every choice of x, y in V(D). We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arcminimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arcset. We show that one can determine in polynomial time the minimum number of new arcs whose addition to D makes the resulting digraph the arcdisjoint union of k antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2detachment.
Let G = (V,E) be a connected graph and let v be a vertex in V. The degree of v, deg(v), equals the number of vertices u that are adjacent to v. The type of vertex v is determined by how deg(v) compares with the degrees deg(u) of all vertices u adjacent to v, that is, does v have any neighbors u whose degree is less than, equal to, or greater than the degree of v? Using this measure, there are 7 possible types of vertices. One can then classify any graph by the number of distinct types of vertices it has. We show that there are 71 classes of connected graphs and 46 classes of trees, as measured by the different types of vertices that they contain. We then raise a number of open questions suggested by this classification of graphs.
This is joint work with Jason T. Hedetniemi (Department of Mathematics, St. Anselm College), Sandra M. Hedetniemi (School of Computing, Clemson University), and Thomas M. Lewis (Department of Mathematics, Furman University).