Perfect 3-Colorings on 4-Regular Graph of Order 8

S. Maity¹ , Sk. R. Islam²

Section:Research Paper, Product Type: Isroset-Journal
Vol.5 , Issue.6 , pp.137-142, Dec-2018

CrossRef-DOI:   https://doi.org/10.26438/ijsrmss/v5i6.137142

Online published on Dec 31, 2018

Copyright © S. Maity, Sk. R. Islam . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

315 Views    227 Downloads    158 Downloads

Abstract :
We study the perfect 3-colorings (also known as the equitable partitions into three parts) on 4-regular graphs of order 8. A perfect n-coloring of a graph is a partition of its vertex set into n parts A1, A2, ..., An such that for all p, q ϵ {1, 2,..., n}, each vertex of Ap is adjacent to apq number of vertices of Aq. The matrix A = (apq) n×n is called quotient matrix or parameter matrix. The concept of a perfect coloring generalizes the concept of completely regular code introduced by P. Delsarte. In particular, we classify all the realizable parameter matrices of perfect 3-colorings on 4-regular graphs of order 8.

Key-Words / Index Term :
Perfect colorings; equitable partition; regular graph

References :
[1] A. L. Gavrilyuk, S. V. Goryainov, “On Perfect 2-Colorings of Johnson Graphs J(v, 3)”, Journal of Combinatorial Designs, Vol. 21, Issue 6, pp. 232-252, June 2013.
[2] A. Neumaier, “Completely regular codes”, Discrete Math, Vol. 106/107, pp.353-360, 1992.
[3] C. Godsil, “Compact graphs and equitable partitions”, Linear Algebra and Its Application, Vol. 255, pp. 259-266, 1997.
[4] P. Delsarte, “An algebraic approach to the association schemes of coding theory”, Philips Res. Rep. Suppl, Vol. 10, pp. 1-97, 1973.
[5] D. B. West, “Introduction To Graph Theory”, Pearson, India, 2001.
[6] M. Meringer, “Fast Generation of Regular Graphs and Construction of Cages”, Journal of Graph Theory, Vol. 30, pp. 137-146, 1999.
[7] D. G. Fon-Der-Flaass, “Perfect 2-colorings of a hypercube”, Siberian Mathematical Journal, Vol. 4 , pp. 923-930, 2007.
[8] D. G. Fon-Der-Flaass, “Perfect 2-colorings of 12-dimensional cube that achieve a bound of correlation immunity”, Siberian Mathematical Journal, Vol.4, pp. 292-295, 2007.
[9] D. G. Fon-Der-Flaass, “A bound on correlation immunity”, Siberian Electronic Mathematical Reports Journal, Vol. 4, pp. 133-135, 2007.
[10] M Alaeiyan, A Mehrabani, “Perfect 3-colorings of the cubic graphs of order 10”, Electronic Journal of Graph Theory and Applications (EJGTA), Vol. 5, Issue 2, pp. 194-206, 2017.
[11] M. Alaeiyan, H. Karami, “Perfect 2-colorings of the generalized Petersen graph”, Proceedings.Mathematical Sciences, Vol. 126, pp. 1-6, 2016.
[12] M. Alaeiyan and A. Abedi, “ Perfect 2-colorings of Johnson graphs J(4, 3), J(4, 3), J(6,3) and Petersen graph”, Ars Combinatoria, (to appear).
[13] S.V. Avgustinovich, I. Y. Mogilnykh, “ Perfect 2-colorings of Johnson graphs J(6,3) and J(7, 3)”.Lecture Notes in Computer Science, pp. 11-19, 2008.
[14] S.V. Avgustinovich, I. Y. Mogilnykh, “Perfect colorings of the Johnson graphs J(8,3) and J(8, 4).With two colors”, Journal of Applied and Industrial Mathematics, Vol. 5, pp. 19 - 30, 2011.