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.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.
[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