Cycle Discrepancy of Cubic Toeplitz Graphs

Authors

  • Laeeq Aslam Punjab University College of Information Technology (PUCIT), University of the Punjab, Lahore, Pakistan
  • Shahzad Sarwar Punjab University College of Information Technology (PUCIT), University of the Punjab, Lahore, Pakistan
  • Muhammad Murtaza Yousaf Punjab University College of Information Technology (PUCIT), University of the Punjab, Lahore, Pakistan
  • Syed Waqar jaffry Punjab University College of Information Technology (PUCIT), University of the Punjab, Lahore, Pakistan

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.

References

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

[2] 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

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

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

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

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

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

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

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

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

Downloads

Published

2018-03-07

Issue

Section

Electrical Engineering and Computer Science