Mathematical Sciences Department, Discrete Mathematics Seminar - Bill Martin, WPI "Dispersed graph labellings" SH202

Floor/Room #

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.



Mathematical Sciences