Perfect 3-colorings of the line graphs of the connected bicubic graphs of order at most 12

Document Type : Research Paper

Author

Department of Mathematics, Faculty of Sciences, Golestan University, Gorgan, Iran

Abstract

Let‎ ‎$G =(V_G‎ , ‎E_G)$‎ ‎be a graph and let $I$ be a finite set of size $m\geq 1$‎. ‎A mapping $T:V_G \rightarrow I$‎ ‎is called a perfect $m$-coloring with a parameter matrix $A = (a_{ij})_{i,j\in I }$‎ ‎of $G$ if it is surjective and for all $i,j$‎, ‎every vertex of color $i$ has $a_{i j}$ neighbors of color $j$‎. ‎In this paper‎, ‎we classify all the realizable parameter matrices of perfect 3-colorings of the line graphs of the connected bicubic graphs of order at most 12‎.

Keywords

References

  1. M. Alaeiyan, Perfect 3-colorings of Heawood graph, International Journal of Nonlinear Analysis and Applications, (1) 12 (2021), 713-717.
  2.  M. Alaeiyan, A. Abedi and M. Alaeiyan, Perfect 3-colorings of the Johnson graph J(6; 3), Bull. Iranian Math. Soc., 46 (2020), 1603-1612.
  3.  M. Alaeiyan and A. Mehrabani, Perfect 3-colorings of the cubic graphs of order 10, Electron. J. Graph Theory Appl., (2) 5 (2017), 194-206.
  4.  M. Alaeiyan, H. Karami and S. Siasat, Perfect 3-colorings of GP(5; 2), GP(6; 2) and GP(7; 2) graphs, J. Indones. Math. Soc., (2) 24 (2018), 47-53.
  5. M. Alaeiyan and A. Mehrabani, Perfect 3-colorings of the cubic graphs of order 8, Armen. J. Math., (2) 10 (2018), 1-9.
  6. M. Alaeiyan and A. Mehrabani, Perfect 3-colorings of the Platonic graph, Iran. J. Sci. Technol. Trans. A Sci., 43 (2019), 1863-1871.
  7. S. Sh. Alamoti, M. Alaeiyan, A. Gilani and M. Golriz, On Perfect 2-Coloring of the bicubic graphs with order up to 12, Punjab University Journal of Mathematics, (8) 52 (2020), 17-25.
  8. S. V. Avgustinovich and I.Yu. Mogilnykh, Perfect 2-colorings of Johnson graphs J(6; 3) and J(7; 3), Lecture Notes in Comput. Sci., 5228 (2008), 11-19.
  9. N. Biggs, Algebraic graph theory, Second Edition, Cambridge University Press, 1993.
  10. D. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs: theory and application, Academic Press, 1980.
  11. C. Godsil and R. Gordon, Algebraic graph theory, Springer, 2001.
  12.  M. A. Lisitsyna, Perfect 3-colorings of prism and Mobius ladder graphs, J. Appl. Ind. Math., (2) 7 (2013), 215-220.
  13. M. A. Lisitsyna, S.V. Avgustinovich and O.G. Parshina, On perfect colorings of in nite multipath graphs, Sib. Elektron. Mat. Izv., 17 (2020), 2084-2095.
  14. M. A. Lisitsyna and S.V. Avgustinovich, On perfect colorings of paths divisible by a matching, J. Appl. Ind. Math., (1) 16 (2022), 98-104.
  15. M. A. Lisitsyna and O.G. Parshina, Perfect colorings of the in nite circulant graph with distances 1 and 2, J. Appl. Ind. Math., (3) 11 (2017), 381-388.
  16.  Z. Liu, Y. Zhao and Y. Zhang, Perfect 3-colorings on 6-regular graphs of order 9, Front. Math. China, 14 (2019), 605-618.
  17. https://doc.sagemath.org/html/en/reference/graphs/index.html
  18.  D. B. West, Introduction to graph theory, Second Edition, Pearson Education, 2001.
Journal of Algebra and Related Topics
Volume 12, Issue 2
January 2025
Pages 99-113

Files

Share

How to cite

Statistics