Distance Between Graphs Using Graph Labelings

Abstract

In \([4]\) Fan Chung Graham investigates the notion of graph labelings and related bandwidth and cutwidth of such labelings when the host graph is a path graph. Motivated by problems presented in \([4]\) and our investigation of designing efficient virtual path layouts for communication networks, we investigate in this note labeling methods on graphs where the host graph is not restricted to a particular kind of graph. In \([2]\) authors introduced a metric on the set of connected simple graphs of a given order which represents load on edges of host graph under some restrictions on bandwidth of such labelings. In communication networks this translates into finding mappings between guest graph and host graph in a way that minimizes the congestion while restricting the delay. In this note, we present optimal mappings between special \(n\)-vertex graphs in \(\mathcal{G}_n\), and compute their distances with respect to the metric introduced in \([2]\). Some open questions are also presented.