Cycle Discrepancy of Cubic Toeplitz Graphs

Laeeq Aslam, Shahzad Sarwar, Muhammad Murtaza Yousaf, Syed Waqar jaffry


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.

Full Text:



S. Abbasi, L. Aslam, 2011, “The cycle discrepancy of three-regular graphs”, Graphs and Combinatorics, Vol. 27, pp. 27–46.

L. Aslam, S. Sarwar, M. M. Yousaf, Waqar ul Qounain, 2016, “Cycle Discrepancy of d-Colorable Graphs”, Pak. J. Engg. & Appl. Sci., Vol. 18, pp. 50-55

J. Beck, W. L. Chen, 1987, “Irregularities of distribution,” Cambridge University press, New York.

J. Beck, W. Fiala, 1981, “Integer making theorems”, Discrete Applied Mathematics, Vol. 3, pp. 1-8.

B. Bollobás, 1988, “Modern graph theory”, Springer-Verlag.

B. Chazelle, 2000, “The discrepancy method: randomness and complexity”, Cambridge University press, New York.

G. A. Dirac, 1952, “Some theorems on abstract graphs”, proc. London math. soc., Vol. s3-2, pp. 69-81.

J. Matousek, 1999, “Geometric discrepancy: an illustrated guide (Algorithms and Combinatorics)”, Springer, Berlin.

J. Spencer, 1985, “Six standard deviations suffice”, Transactions of the American mathematical society, Vol. 289, pp. 679-706.

W. Chen, A. Srivastav, and G. Travaglini, 2014, “A Panorama of Discrepancy Theory”, Lecture Notes in Mathematics, Springer International Publishing.

Copyright (c) 2018 Pakistan Journal of Engineering and Applied Sciences

Powered By KICS