A quadrangular embedding of a complete graph is a minimal (smallest order) quadrangulation of a surface. Divisibility conditions based on Euler’s formula give necessary conditions for such embeddings to exist. In 1989 Hartsfield and Ringel showed that quadrangular complete graph embeddings exist in half of the possible cases. We show existence in the remaining cases. In the orientable case we use the ‘graphical surface’ technique due to Craft, combined with voltage graphs. In the nonorientable case we use the ‘diamond sum’ techique originally due to Bouchet. Both results were apparently also proved, but never published, in the 1990s by Chen, Lawrencenko and Yang (orientable case, using current graphs) and Hartsfield (nonorientable case). Our techniques also yield some results on minimal quadrangulations where the graph is not a complete graph.
This is joint work with Wenzhong Liu, Dong Ye and Xiaoya Zha.
Oporowski, Oxley, and Thomas showed that there is a function f such that every 3-connected graph of sufficient order, f(n), contains a minor isomorphic to a wheel, Wn, or K3, n. We prove an analogous result for immersion, giving the unavoidable immersions of 3-edge-connected graphs, and a conjecture for the unavoidable immersions of 4-edge-connected graphs.
Tutte and Thomas and Yu proved that 4-connected planar and projective-planar graphs, respectively, are hamiltonian. Grünbaum and Nash-Williams conjecture that 4-connected toroidal and Klein bottle graphs are hamiltonian. Thomassen constructed counterexamples to edge-hamiltonicity of four-connected toroidal and Klein bottle graphs. Ellingham and Marshall contribute to the characterization of four-connected toroidal graphs in which some edge is not on a hamilton cycle, showing a sort of criticality of Thomassen’s counterexamples and their generalizations. We contribute to the characterization of 4-connected Klein bottle graphs that have some edge not on a hamilton cycle, showing a criticality similar to that in Ellingham and Marshall’s toroidal graphs.
Abstract: A laminar family is a collection of sets such that if two sets intersect, one is contained in the other. A laminar matroid is defined in terms of a laminar family 𝒜 and a capacity function c:𝒜→ ℕ, a set I being independent if |I ∩ A| ≤ c(A) for all A ∈ 𝒜. It is not hard to show that the class of laminar matroids is minor closed. This first half of this talk will describe the set of excluded minors for this class. In addition, it will present a way to construct all laminar matroids using basic operations and will compare the class of laminar matroids to other well-known classes of matroids. The second half will present generalizations of this class and discuss some structural results for these related classes. This is joint work with James Oxley.
A permutation graph is a graph that can be derived from a permutation, where the vertices correspond to letters of the permutation, and the edges represent inversions. This talk will explain some theory of the structure of permutation graphs. In the 3-regular case, we give a complete characterization, and we enumerate the 3-regular permutation graphs on n vertices with a recursive formula.
Using the beta invariant and the characteristic polynomial of a matroid M, we prove that if G is a 3-connected graph such that the chromatic polynomial of G is equal to the chromatic polynomial of a wheel graph, then G is isomorphic to the wheel graph. And we show a splitting formula of the beta invariant of a general parallel connection across a 3-point line and 3-sum of two matroids and how this result is related to the connectivity condition of the chromatic polynomial result.
Let ℕ be the set of all nonnegative integers. A set A ⊂ ℕ is called a basis of ℕ if every sufficiently large integer is a sum of h elements from A, for some h. The smallest such h is called the order of A. For example, the squares form a basis of order 4 and the primes conjecturally form a basis of order 3 of ℕ. Erdős and Graham asked the following questions. If A is a basis of ℕ and a ∈ A, when is A \ { a } still a basis? It turns out that this is the case for all a ∈ A with a finite number of exceptions. If A \ { a } is still a basis, what can we say about its order? These questions and related questions have been extensively studied. In this talk, we address these questions in the more general setting of an abelian group in place of ℕ. This is joint work with Victor Lambert and Alain Plagne.
Path-pairability is a graph theoretical notion that emerged from a practical networking problem introduced by Csaba, Faudree, Gyárfás, Lehel, and Schelp, and further studied by Faudree, Gyárfás, and Lehel; and by Kubicka, Kubicki and Lehel. A graph is path-pairable if for any pairing of its vertices there exist edge disjoint paths joining the vertices in each pair. One central question in path-pairability is how small can be the maximum degree of a path-pairable graph. Faudree, Gyárfás, and Lehel showed that a path-pairable graph on n vertices has maximum degree at least log n / loglog n. To date the best known constructions are due to Győri, Mezei, and Mészáros, and they offer examples of path-pairable graphs with maximum degree c · log n. In my talk I will summarize the evolution of the topic, present the latest known results, and discuss possible directions of future research.
The speaker once conjectured that for every pair of 3-sets of integers, the integers could be colored with 2 colors so that no translate in the integers of either set would be monochromatic. This turned out to be not true. However, given the two 3-sets, there always is a coloring of the integers with 3 colors which will “forbid” monochromatic translates of each. More generally, for any k sets of integers, each with at least 2 elements, there is a coloring of the integers with k + 1 colors which forbids monochromatic translates of each set. Many questions remain.
An oriented hypergraph provides for the natural generalization of graph theoretic concepts through its locally signed graphic sub-structure. In this talk, we will discuss how sub-monic embeddings produce hypergraphic versions of Sachs’ Coefficient Theorem and Chaiken’s All Minors Matrix-tree Theorem for hypergraphic adjacency and Laplacian matrices. As a consequence, an interesting approach to examine determinant and permanent bounds will also be discussed.
A graph is said to have the fixed vertex property iff every graph endomorphism fixes a vertex. The whole theory for the fixed point property for ordered sets can, via the right gadgets, be embedded into the theory for the fixed vertex property. The classical question whether the product of two ordered sets with the fixed point property has the fixed point property, too, (which is resolved affirmative for finite ordered sets) has not just one, but at least four analogues for the fixed vertex property: The answer for the direct product is, surprisingly, negative. The question for lexicographic products is surprisingly difficult and unresolved. For the Cartesian product, progress towards a positive answer has been made. Finally, the question for the strong product may be the appropriate analogue for the corresponding question for ordered sets and insights into strong products might lead to insights on products of infinite ordered sets.
Let C be the set of all connected graphs on vertex set [n]. Then C is endowed with the following natural partial ordering: for G, H ∈ C, let G ≤ H if G is a subgraph of H. The poset (C, ≤) is graded, each level containing the connected graphs with the same number of edges. We prove that (C, ≤) has the Sperner property, namely that the largest antichain of (C, ≤) is equal to its largest sized level. This answers a question of Katona.