Mathematical Sciences Department
Discrete Mathematics Seminar
Bill Martin, WPI
Monday, February 6, 2023
4:00 pm - 4:50 pm
Stratton Hall 202
Title: Dispersed graph labellings
Abstract: I will discuss a fun problem that I recently worked on with Doug Stinson (Waterloo). Let G be a graph with vertex set V and path-length distance function d(.,.). A k-dispersed labeling of G is a linear ordering v1, v2, ..., vn of the vertices such that d(vi-1, vi ) ≤ k for all i=2,...,n. Finding the best k for a given graph is an NP-hard problem but we have bounds and can find exact values in special cases. I predict you can do better than I have done.