Workshop 2013 - Abstracts


James Oxley  (Keynote)     —     Inductive tools for handling internally 4-connected binary matroids and graphs

A matroid is 3-connected if it does not break up as a 1-sum or a 2-sum. Numerous problems for matroids reduce easily to the study of 3-connected matroids. Two powerful inductive tools for dealing with 3-connected matroids are Tutte's Wheels-and-Whirls Theorem and Seymour's Splitter Theorem. For several years, Carolyn Chun, Dillon Mayhew, and I have been seeking analogues of these theorems for internally 4-connected binary matroids, that is, binary matroids that do not break up as a 1-, 2-, or 3-sum. The class of such matroids includes the cycle matroids of internally 4-connected graphs, those 3-connected simple graphs that are 4-connected except for the possible presence of degree-3 vertices. This talk will report on our progress towards finding these analogues.

Stan Dziobiak     —     Obstructions of apex classes of graphs

The famous Graph Minor Theorem of Robertson and Seymour states that every minor-closed class C of graphs can be characterized by a finite list of minor-minimal non-members, called obstructions of C, and denoted by ob(C). Given a minor-closed class of graphs C and its obstruction set ob(C), the problem of determining ob(C*) (where C* denotes the class of graphs that contain a vertex whose deletion leaves a graph in C) is already very hard if C is the class of planar graphs, and has only been solved (completely) for a few non-trivial minor-closed classes of graphs C. In this talk we present our solutions to this problem for outerplanar graphs, cactus graphs, and report on the progress towards the solution for series-parallel graphs.

Eric Gottlieb     —     Discrete fair division using posets

Consider the problem of allocating a number of discrete goods among a set of individuals. If each individual ranks the items linearly according to their preferences, then an individual's ranking naturally induces a partial order M on sets of the items. M induces a partial order on the set of all allocations of items to individuals. M has been studied in different contexts by Stanley and others.

Each individual's partial order on allocations can then be viewed as a ballot in an election in which the allocations play the role of the candidates. In earlier work, some collaborators and I proposed a method for tabulating ballots when preferences are partially ordered. Cullinan, Hsiao, and Polett proposed a computationally simpler approach and proved that it has some nice properties. I will give some preliminary observations on the application of their approach to the fair division problem.

Daniel Guillot     —     Coloring graphs drawn with no dependent crossings

Král and Stacho showed that if a graph is drawn in the plane so that the vertices incident with crossed edges are all distinct, then the graph admits a 5-coloring. In the talk, I will discuss extensions of this result to graphs drawn on other surfaces.

Ademir Hujdurovic     —     Pentavalent symmetric bicirculants

A graph X is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices (u, v) and (u',v'), there is an automorphism f of X, such that f(u) = u' and f(v) = v'. A bicirculant is a graph admitting an automorphism with two cycles of equal length in its cycle decomposition.

The most famous example of a symmetric biciruculant is the Petersen graph, which is cubic. All cubic and tetravalent symmetric bicirculants are known. In this talk I will present a classification of pentavalent symmetric bicirculants. This is joint work with Iva Antončič and Klavdija Kutnar.

James Oxley (see top of page)

Bette Catherine Putnam     —     Bicircular Matroids with Circuits of Few Sizes

Matroids designs are defined to be matroids in which the hyperplanes all have the same size. The dual of a matroid design is a matroid with all circuits of the same size, called a dual matroid design. The connected bicircular dual matroid designs have been characterized previously. In addition, these results have been extended to connected bicircular matroids with circuits of two sizes in the case that the associated graph is a subdivision of a 3-connected graph. In this talk, we will use a graph theoretic approach to discuss the characterizations of bicircular matroids with circuits of two and three sizes. We will characterize the associated graph of a bicircular matroid with circuits of two sizes. Moreover, we will provide a characterization of connected bicircular matroids with circuits of three sizes in the case that the associated graph is a subdivision of a 3-connected graph.

Jesse Taylor     —     On matroid minors that guarantee their duals as minors

A fundamental operation for matroids is the construction of the dual. This talk solves the problem of determining all 3-connected binary matroids N such that, whenever a 3-connected binary matroid M has an N-minor, and M is large enough, M also has the dual of N as a minor. No previous familiarity with matroids will be assumed.

Shaohui Wang     —     Multiplicative Zagreb indices of k-trees

Let G be a graph with vertex set V(G) and edge set E(G). The first generalized multiplicative Zagreb index of G is ∏1,c(G) = ∏vV(G) d(v)c, for a real number c > 0, and the second multiplicative Zagreb index is ∏2(G) = ∏uvE(G) d(u)d(v), where d(u), d(v) are the degrees of the vertices of u,v. The multiplicative Zagreb indices have been the focus of considerable research in computational chemistry dating back to Narumi and Katayama in 1980s. In this paper, we generalize the Narumi-Katayama index and the first multiplicative index, where c = 1, 2, respectively, and extend the results of Gutman to the generalized tree, the k-tree, where the results of Gutman are for k = 1. Additionally, we characterize the extremal graphs and determine the exact bounds of these indices of k-trees, which attain the lower and upper bounds.

Dong Ye     —     Perfect matchings and resonant patterns of fullerenes

A fullerene is a 3-connected plane graph with only pentagonal faces and hexagonal faces. Let F be a fullerene graph. A perfect matching of F is a set M of disjoint edges such that every vertex of F is incident with exactly one edge in M. A resonant pattern of a fullerene graph F is a set H of disjoint hexagons whose deletion results in a subgraph with a perfect matching. In other words, F has a perfect matching M such that the edges of every hexagon in H alternate between M and E(G) \ M. In this talk, we will survey some old and new results in this direction.

Return to the homepage.

Last modified September 14, 2018