COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2016

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 arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to D makes the resulting digraph the arc-disjoint 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 2-detachment.

Previous Talks

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).