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

Monday, February 6, 2023
4:00 pm to 4:50 pm
Location
Floor/Room #
202
Preview

flyer

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.

Audience(s)

DEPARTMENT(S):

Mathematical Sciences