The regular seminar time is Wednesday, 3:35 - 4:25 p.m. The seminar takes place in person in Stevenson Center 1432. The seminar coordinator this semester is Anna Yu, anna.c.yu at vanderbilt.edu . Some seminars may be at unusual times, or may be given as Zoom talks.
Vertex-switching reconstruction – Mark Ellingham (Vanderbilt University)
The vertex-switching reconstruction problem (VSRP) was introduced by Richard Stanley in 1985. A switching at a vertex v in a simple graph G removes all edges from v to N(v) and replaces them by edges from v to V(G)-N(v)-{v}, forming a graph Gv. The vertex-switching deck of G is the collection (multiset) of isomorphism classes of the graphs Gv for all v in V(G). A graph is vertex-switching reconstructible if this deck determines G up to isomorphism. Stanley showed that every n-vertex graph is vertex-switching reconstructible provided n is not divisible by 4. There are graphs on 4 vertices that are not vertex-switching reconstructible, but the question remains open for larger graphs with order divisible by 4. In 1992 Royle and the speaker showed that triangle-free graphs are vertex-switching reconstructible. In this talk we discuss these results and the algebraic techniques used to prove them, in the hope of generating new interest in the VSRP.
On Pell numbers representable as product of two generalized Fibonacci numbers – J.C. Saunders (Middle Tennessee State University)
A generalization of the well-known Fibonacci sequence is the k-Fibonacci sequence with some fixed integer k ≥ 2. The first k terms of this sequence are 0, 0, . . . , 1, and each term afterwards is the sum of the preceding k terms. In this paper, we find all Pell numbers that can be written as product of two k-Fibonacci numbers. The proof of our main theorem uses lower bounds for linear forms in logarithms, properties of continued fractions, and a variation of a result of Dujella and Petho in Diophantine approximation. This work generalizes a prior result of Alekseyev which dealt with determining the intersection of the Fibonacci and Pell sequences, a work of Ddamulira, Luca and Rakotomalala who searched for Pell numbers which are products of two Fibonacci numbers, and a result of Bravo, Gómez and Herrera who found all Pell numbers appearing in the k-Fibonacci sequence.
On graphs with girth at least five achieving Steffen's edge coloring bound – Anna Yu (Vanderbilt University)
Vizing and Gupta showed that the chromatic index χ'(G) of a graph G is bounded above by Δ(G) + μ(G), where Δ(G) and μ(G) denote the maximum degree and the maximum multiplicity of G, respectively. Steffen refined this bound, proving that χ'(G) ≤ Δ(G) + ⌈ μ(G)/⌊ g(G)/2 ⌋ ⌉, where g(G) is the girth of the graph G. A ring graph is a graph obtained from a cycle by duplicating some edges. The equality in Steffen's bound is achieved by ring graphs of the form μ Cg, obtained from an odd cycle Cg by duplicating each edge μ times. We answer two questions posed by Stiebitz et al. regarding the characterization of graphs which achieve Steffen's bound. In particular, we show that if G is a critical graph which achieves Steffen's bound with g(G)≥ 5 and χ'(G)≥ Δ+2, then G must be a ring graph of odd girth. This is joint work with Guantao Chen, Alireza Fiujlaali, and Jessica McDonald.
On the extremal structure of (n,k,H)-graphs – Stacie Baumann (College of Charleston)
A graph G is an (n,k,H)-graph if |V(G)| = n and every induced subgraph of G on k vertices contains H as a (not necessarily induced) subgraph. A minimum (n,k,H)-graph is an (n,k,H)-graph with the minimum number of edges among all (n,k,H)-graphs.
Turán's Theorem (taking complements of graphs in the traditional statement) finds the minimum (n,k,K2)-graph. We first generalize this result by determining the structure of minimum (n,k,Kt)-graphs. We then discuss minimum (n,k,H)-graphs for several other graphs H.
Next, we consider a natural saturation problem related to these graphs. An inclusion-minimal (n,k,H)-graph is an (n,k,H)-graph with the property that deleting any edge produces an induced subgraph on k vertices that does not contain H as a subgraph. Erdős, Hajnal, and Moon showed that the inclusion-minimal (n,k,K2)-graph with the maximum number of edges is (k-2)K1 + Knk+2. We present recent progress towards determining the maximum number of edges in inclusion-minimal (n,k,Kt)-graphs.
This is joint work with Joseph Briggs and John McMann.
Mark Ellingham / mark.ellingham at vanderbilt.edu