CAG Schedule of Talks: Fall 2016

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Fall 2016

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

Schedule for Talks:

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 Bang-Jensen Antistrong Digraphs

Upcoming Talks

Antistrong Digraphs
Joergen Bang-Jensen
Department of Mathematics and Computer Science
University of Southern Denmark, Odense, Denmark
Friday Oct. 21, 2:30pm, MacLaurin D 101

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

Classifying Graphs by Degrees
Stephen T. Hedetniemi, Professor Emeritus
School of Computing, Clemson University
Friday September 9, 3:30pm, ECS 660

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


CAG Schedule of Talks: Fall 2016 / maintained by Wendy Myrvold / wendym@csc.UVic.ca / revised Oct. 13, 2016