Cycle Discrepancy of Cubic Toeplitz Graphs

Abstract

A Toeplitz graph is one whose adjacency matrix is a Toeplitz matrix. A Toeplitz matrix is also known as a constant diagonal matrix. This paper defines cubic Toeplitz graphs and establishes that the cycle discrepancy of a cubic Toeplitz graph is at most 1. That is cycdisc(G) ≤ 1, where G is a cubic Toeplitz graph. Further this bound is shown to be tight.