Abstracts
[Note: this webpage last modified Wednesday, 16-May-2012 09:50:31 EDT]
The abstracts for the talks are posted here. The abstracts are sorted alphabetically by the last name of the presenter. You can download a PDF with all abstracts here. You can download the slides for a given talk by clicking on the "slides from talk" link.
Mod n representations of complete multipartite graphs
Reza Akhtar
Miami University
email: akhtarr@muohio.edu
A graph G has a representation modulo r if there exists an injective map f : V (G) →{0, 1, ..., r-1} such that vertices u and v are adjacent if and only if gcd(f(u)- f(v), r) = 1; the representation number rep(G) is the smallest positive integer r for which G has a representation modulo r. We describe some recent work (joint with Dan Pritikin and Tony Evans) on this parameter in the case that G is a complete multipartite graph.
Animating Graph Theory
David J. Anderson
EdgeCase
email: dave@edgecase.com
Marrying the ubiquity of the web with the power of animation will help make Graph Theory more accessible and understandable to students, mathematicians, and the curious. This presentation provides a rationale for this perspective, shows technology that can perform web-based animation, and specifies the conceptual development of a system that will allow users to create, access, and reuse animatable Graph Theory algorithms.
Regular and bi-regular cages
Gabriela Araujo-Pardo
Instituto de Matemáaticas
Universidad Nacional Autónoma de Mexico
email: garaujo@math.unam.mx
In this talk, we give a brief summary of the Cage Problem and the relationship between cages of even girth that attain the Moore Bound and generalized polygons. Moreover, we investigate the same problem for bi-regular graphs.
We will present an overview of our results on these topics, and more specically, the construction of regular and bi-regular graphs with small degree and xed girth based on the use of geometric concepts and tools. We will emphasize that, in contrast to regular graphs, the bi-regular graphs we obtain using our constructions are best possible { bi- regular cages.
Constructing universal graphs
Steve Butler
Iowa State University
email: butler@iastate.edu
Given a family of graphs we can work to construct the smallest graph which contains as induced subgraphs each graph in the family. We show that if we choose the family of all graphs on n vertices with bounded maximum degree that we can use some simple tools to construct near-optimal graphs. This construction also extends to multigraphs and digraphs.
Secret sharing scheme and multipartite graphs
Mustafa Atici
Western Kentucky University
email: mustafa.atici@wku.edu
Let P = {P1, P2, ..., Pn} be set of participant and Γ = {Bi | Bi ⊂ P , 1≤ i ≤¤ k} be access structure. Vector space secret sharing scheme realizing access structure Γ requires existence of function φ : P → (Zp )d , where p is a prime number and d &≥q;2 is an integer, satisfying the following condition: (1, 0, 0, 0, ..., 0) = < φ(Pi ) : Pi ⇔ B > ∈ Γ = {B1, B2 , ..., Bk }. There is no known algorithm to construct such a function φ in general. Constructions are mainly done by trial and error. In this talk, we give a polynomial algorithm to construct a φ function for certain type of access structures. That is access structures that correspond edge set of multipartite graph G.
Vertex-transitive graphs
Ted Dobson
Mississippi State University and the University of Primorska
email: dobson@math.msstate.edu
A graph Γ is vertex-transitive if its automorphism group Aut(Γ) acts transitively on the vertex set V(Γ) of the graph. That is, if for every x and y in V(Γ), there exists ψ in Aut(Γ) such that ψ(x) = y. Intuitively, a graph is vertex-transitive if it is not possible to distinguish between vertices. Many important graphs are vertex-transitive graphs (e.g. the Petersen graph, the Coxeter graph), and vertex-transitive graphs are important in chemistry and theoretical computer science, amongst other areas. Recently, vertex-transitive graphs received a fair amount of interest.
The purpose of this talk is to introduce what I consider some of the main problems (or perhaps just some of my favorite problems) in the study of vertex-transitive graphs, as well as indicate the kinds of results that have been and are currently being obtained concerning these problems. These problems include determining the full automorphism group of a vertex-transitive graph, determining necessary and sufficient conditions for two vertex-transitive graphs to be isomorphic, and Lovász's conjecture that every connected a vertex-transitive graph contains a Hamilton path. By determining the automorphism group, we mean either an explicit list of groups, or a polynomial time algorithm to list a set of generators of the automorphism group. By "necessary and sufficient conditions for two graphs to be isomorphic" it is usually meant an explicit list L of maps, and two vertex-transitive graphs with a common minimal transitive subgroup are isomorphic if and only if they are isomorphic by a map on L.
Counting independent sets of a fixed size in graphs with given minimal degree
John Engbers
University of Notre Dame
email: jengbers@nd.edu
Given a family of graphs, we can ask which graph in the family has the largest number independent sets, and we can also ask which graph in the family has the largest number of independent sets of a fixed size. Often, but not always, the extremal graphs that answer these two questions turn out to be the same. We will explore these questions within the family of graphs on n vertices with given minimal degree δ and will show that the answer to these questions is almost always the complete bipartite graph Kδ,n-δ . We will also highlight some open questions. This is joint work with David Galvin.
Magic rectangle sets and ordered distance antimagic graphs
Dalibor Fronček
University of Minnesota Duluth
email: dalibor@d.umn.edu
Magic rectangles are a generalization of the well-known notion of magic squares. A magic rectangle M R(a, b) is an a × b array whose entries are {1, 2, . . . , ab}, each appearing once, with all its row sums equal and with all its column sums equal. T. Harmuth proved in 1861 that a magic rectangle M R(a, b) exists if and only if a, b > 1, ab > 4, and a ≡ b (mod 2).
We generalize this notion one step further by defining magic rectangle sets. A magic rectangle set M RS(a, b; c) is a collection of c arrays a × b whose entries are {1, 2, . . . , abc}, each appearing once, with all row sums in every rectangle equal to a constant s and all column sums in every rectangle equal to a constant t.
We present constructions of some infinite classes of magic rectangle sets and explain our motivation for their study by showing a connection to incomplete handicap tournaments and ordered distance antimagic graphs.
An ordered distance antimagic labeling of a graph G(V, E) with n vertices is a bi-jection f→: V→ {1, 2, . . . , n} with the property that f→(xi ) = i and the sequence (w(x1 ), w(x2 ), . . . , w(xn )) forms an increasing arithmetic progression with difference one where w(xi ), the weight of vertex xi, is the sum of the labels of all neighbors of xi. A graph G is an ordered distance antimagic graph if it allows an ordered distance antimagic labeling.
Colouring regular graphs without large independent sets
David Galvin
University of Notre Dame
email: galvin1@nd.edu
Among all n-vertex, d-regular graphs, which one admits the most proper q-colourings for each q? There's an appealing conjecture, that when 2d divides n the answer is the same for every q: it's the disjoint union of n/2d copies of Kd,d, the complete bipartite graph with d vertices in each partite set.
If we restrict to bipartite graphs, the conjecture is true. For regular graphs which are close to being bipartite, in the sense that they have an independent set consisting of roughly half the vertices, an asymptotic version of the conjecture is known.
Here we look at the other side of the picture. We put an upper bound on the number of q-colourings admitted by a regular graph in terms of the independence number of the graph, and so show that the conjecture concerning Kd,d's is true for every graph that is not close to being bipartite.
Extraordinary Subsets and a Partial Order
Ralph P. Grimaldi
Rose-Hulman Institute of Technology
email: grimaldi@rose-hulman.edu
For a positive integer n, a subset S of [n] = {1, 2, . . . , n} is called extraordinary when the minimal element in S is the same as the size of S. If we let an count the number of extraordinary subsets of [n], we find that an = Fn , the n-th Fibonacci number. Following this, we examine a(n, k), the number of times the positive integer k appears among the an extraordinary subsets of [n]. Then we look to
(i) tn, which counts the total number of elements (repeats are counted) that occur among the an extraordinary subsets of [n]; and,
(ii) sn , which is the sum of all the elements (repeats are counted) that occur among the an extraordinary subsets of [n].
Finally, for a given n, we introduce a partial order for the an subsets of [n] and determine a formula for the number of edges that occur in the Hasse diagram for the partial order.
Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
Ping Hu
University of Illinois at Urbana-Champaign
email: pinghu1@illinois.edu
Erdőos proposed the problem of determining exQ(n;C2t), i.e. to determine the maximum number of edges that a subgraph of the n-dimensional hypercube containing no C2t can have.
We modify slightly Razborov's flag algebra machinery to be suitable for the hypercube. We use this modied method to show that the maximum number of edges in a subgraph of the n-dimensional hypercube containing no 4-cycle is at most 0.6068 times the number of edges in the hypercube. For subgraphs containing no 6-cycle, we improve the upper bound on the proportion of edges from sqr(2)-1 to 0.3755.
(Joint work with Jozsef Balogh, Bernard Lidicky, and Hong Liu.)
Light Spanners with Stack and Queue Charging Schemes
Hao-Hsiang Hung
Emory University
emal: hhung2@emory.edu
We consider the problem of decomposing light spanners in some minor-closed graph families. We provide an approach employing two charge patterns. That is, given a spanning tree T within a light spanner, we partition the remaining edges into a bounded number of classes, each of which is either "stack like" or "queue like" with respect to an Euler tour of T . We show that this approach works well for bounded genus graphs and could attack subfamilies of bounded genus graphs, but is not enough for the general case. We could counterexamples for such a mixed scheme.
Long Cycles Represented by Paths
Robert E. Jamison and Douglas B. West
University of Illinois, Urbana-Champaign
email: rejamis@illinois.edu, west@math.uiuc.edu
Many graph classes are defined by the following paradigm: each vertex is assigned something measuring its size and something measuring its tolerance. If the combined sizes exceed the combined tolerances, then there is a conflict and the corresponding vertices are adjacent in a conflict-tolerance graph. In this talk we construct such representations for long chordless cycles in the case that the "sizes" are paths Pr in Kn and "conflict" occurs when two paths contain a common Pq for some fixed q < r.
Rainbow spanning trees in Abelian groups
Bill Kinnersley
University of Illinois at Urbana-Champaign
email: wkinner2@illinois.edu
Given an additive Abelian group A, let KA denote the edge-colored complete graph in which the vertices are the elements of A, and edge xy has color x+y. Which trees appear as rainbow subgraphs in KA (that is, subgraphs with no two edges of the same color)? This question naturally gives rise to a labeling problem with close ties to harmonious, elegant, and cordial labeling.
In this talk, we provide some necessary and some sufficient conditions for a tree T to embed as a rainbow spanning tree in KA. When A = {Z}n, a conjecture due to Hovey would imply that every n-vertex tree embeds as a rainbow spanning tree in KA; we show that the analogous statement fails whenever A is non-cyclic. With computer assistance, for every Abelian group A of order at most 20, we determine all trees on |A| vertices that fail to embed as rainbow spanning trees in KA. (There are not very many!)
This is joint work with Robert E. Jamison.
Extending graph choosability results to paintability
Thomas Mahoney
University of Illinois at Urbana-Champaign
email: tmahone2@illinois.edu
Introduced independently by Schauz and by Zhu, the Marker/Remover game is an on-line version of list coloring. The resulting graph parameter, paintability, is at least the chromatic number (the choosability). We discuss the extension of various choosability results to paintability. These include the analogue of Ohba's conjecture, bounds on the paintability of complete bipartite graphs, characterization of 3-paint-critical graphs, and equality of paintability and chromatic number for claw-free perfect graphs with no 4-clique.In more detail, we then introduce and study sum-paintability, the analogue of sum-choosability.
List and Online List Variations of Vertex Ranking
Daniel McDonald
University of Illinois at Urbana-Champaign
email: dmcdona4@illinois.edu
A vertex ranking of a graph G is a labeling of its vertices with positive integers such that any path whose endpoints have the same label contains a larger label; applications of rankings include VLSI design, parallel computing, and factory scheduling. The list rank number of G is the least positive integer k such that if each vertex of G is assigned a set of k potential labels, G can always be ranked by labeling each vertex with a label from its assigned list. We formulate an online version of the list rank number and compute the online list rank number of paths and cycles as well as the list rank number of trees with many more leaves than internal vertices.
k-Partiteness of the Complements of Cographs
Terry McKee
Wright State University
email: terry.mckee@wright.edu
A graph is a cograph if and only if it reduces to an edgeless graph by repeatedly taking complements within components, which is known to be equivalent to every induced subpath having at most two edges. I discuss various sorts of characterizations of those nontrivial connected cographs for which all the nontrivial components of the complement are complete k-partite. For instance, one of several characterizations for the bipartite case is that every induced subtree is a path with at most two edges.
The Jacobsthal Subcube of the Hypercube
John Rickert
Rose-Hulman Institute of Technology
email: john.rickert@rose-hulman.edu
We study a special subset of the n-dimensional hypercube, the Jacobsthal subcube, dened recursively by only including strings of 0s and 1s that can be written by combining the strings 0, 01, and 11. The number of vertices in the subcube is given by the n-th Jacobsthal number Jn, dened by the Fibonacci-like recurrence relation Jn = Jn-1 + 2Jn-2, J0 = 1, J1 = 1. We count the number of edges in the Jacobsthal subcube and discover Hamiltonian paths. This is joint work with Ralph Grimaldi and Tom Langley.
K7 in the torus: a long story
Thomas Tucker
Colgate University, Hamilton, New York
email: ttucker@colgate.edu
The embedding of K7 in the torus has played an important role in topological graph theory. It is, of course, the rst step in the Heawood Map Color Theorem, but it also inspired current maps, voltage graphs, rotation systems, Cayley maps, and chirality for regular maps. We will try to trace out parts of the story, including a little known tale from Jack Edmonds about how a conjecture in Coxeter and Moser about chiral maps led him to rotation systems. We will nish with an absurdly simple proof that regular (re exible) maps have clique number 2,3,4, or 6, a result previously obtained only through elaborate algebraic arguments.
Sliding colours in graphs
Landan Hicks, Marc Lipman, and Matt Walsh*
Indiana University - Purdue University Fort Wayne
email: walshm@ipfw.edu
The vertices of a graph G are coloured improperly, but in a way such that some permuta- tion of the colouring will be proper. We want to restore the proper colouring; we can do so by removing the colours on some vertices (creating "holes" in the colouring) and sliding colours from vertices into adjacent holes. What is the minimum number of holes required to restore any such scrambled colouring? We give partial answers to these questions, and discuss some variations on the theme.
Rainbow edge-coloring and rainbow domination
Douglas B. West
University of Illinois at Urbana-Champaign
email: west@math.uiuc.edu
Let G be an edge-colored graph with n vertices. A rainbow subgraph is a subgraph whose edges have distinct colors. The rainbow edge-chromatic number of G, written \widehat{χ}(G), is the minimum number of rainbow matchings needed to cover E(G). An edge-colored graph is t-tolerant if it contains no monochromatic star with t + 1 edges. If G is t-tolerant, then \widehat{χ} (G) < t(t+1)n ln n, and examples exist with \widehat{χ} (G)≥ t/2(n -1). The rainbow domination number, written \widehat{γ} (G), is the minimum number of disjoint rainbow stars needed to cover V(G). For t-tolerant edge-colored n-vertex graphs, we generalize classical bounds on the domination number:
(1) \widehat{γ}(G) ≤ n(1+ln)/k (where k =δ(G) +1 ), and
(2) \widehat{&gγ}(G) ≤ nt/(t+1) when G has no isolated vertices.
We also characterize the edge-colored graphs achieving equality in the latter bound. This joint work with Timothy D. LeSaulnier.
Clones in Bicircular Matroids
Xiangqian Zhou (Joe)
Department of Mathematics and Statistics, Wright State University
email: xiangqian.zhou@wright.edu
There are two fundamental classes of matroids related to graphs: the well-known one is the class of graphic matroids where a circuit of the matroid is the edge set of a cycle in the graph; the other one is the class of bicircular matroids where a circuit of the matroid is the edge set of a minimal connected subgraph containing at least two cycles of the graph.
Two elements in a matroid are clones if the map that interchanges the two and xes all other elements is an automorphism of the matroid. Clones have recently become an interesting subject in matroid representation theory. In the talk, we will describe exactly when two elements of a bicircular matroid form a clonal pair. This is joint work with Daniel Slilaty and Jakayla Robbins.