Distance between graphs using graph labelings

Kiran R. Bhutani, Bilal Khan

Research output: Contribution to journalArticlepeer-review


In [4] Fan Chung Graham investigates 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 G n and compute their distances with respect to the metric introduced in [2]. Some open questions are also presented.

Original languageEnglish (US)
Pages (from-to)45-52
Number of pages8
JournalArs Combinatoria
StatePublished - Oct 2005
Externally publishedYes


  • Distance between graphs
  • Graph embeddings
  • Virtual path layout

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Distance between graphs using graph labelings'. Together they form a unique fingerprint.

Cite this