Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2017; 54(6): 1883-1891

Online first article November 6, 2017      Printed November 30, 2017

https://doi.org/10.4134/BKMS.b160168

Copyright © The Korean Mathematical Society.

Enumeration of optimally labelled graphs of bandwidth 2

Gab-Byung Chae, MinSeok Cheong, Sang-Mok Kim

Wonkwang University, Korea University, Kwangwoon University

Abstract

An optimally labelled graph of bandwidth 2 is an ordered pair $(G, f)$ where $G$ is a simple graph with $bw(G)=2$ and $f : V(G) \rightarrow [n]$ is a bijection such that $bw(G, f)=2$. In this paper, the number of optimally labelled graphs of bandwidth two of order $n$ is enumerated by counting linear forests.

Keywords: enumeration, linear discrepancy, bandwidth

MSC numbers: 05C30