INDUCED \(nK_{2}\) DECOMPOSITION OF INFINITE SQUARE GRIDS AND INFINITE HEXAGONAL GRIDS

Dinesan Deepthy     (GITAM University, Bangalore, India)
Joseph Varghese Kureethara     (Christ University, Bangalore, India)

Abstract


The induced \(nK_2\) decomposition of infinite square grids and hexagonal grids are described here. We use the multi-level distance edge labeling as an effective technique in the decomposition of square grids. If the edges are adjacent, then their color difference is at least 2 and if they are separated by exactly a single edge, then their colors must be distinct. Only non-negative integers are used for labeling. The proposed partitioning technique per the edge labels to get the induced \(nK_2\) decomposition of the ladder graph is the square grid and the hexagonal grid.


Keywords


Distance labelling, Channel assignment, \(L(h,k)\)-colouring, Rectangular grid, Hexagonal grid.

Full Text:

PDF

References


  1. Balci M.A., Dündar P. Average edge-distance in graphs. Selçuk J. Appl. Math., 2010. Vol. 11, No. 2. P. 63–70.
  2. Chartrand G., Lesniak L., Zhang P. Graphs and Digraphs. 6th Ed. Boca Raton, US: CRC Press, 2016. 640 p. DOI: 10.1201/b19731
  3.  Deepthy D., Kureethara J.V. On \(L'(2,1)\)–edge coloring number of regular grids. An. Şt. Univ. Ovidius Constanţa, 2019. Vol. 27, No. 3. P. 65–81.  DOI: 10.2478/auom-2019-0034
  4. Deepthy D., Kureethara J.V. \(L'(2,1)\)–edge coloring of trees and cartesian product of path graphs. Int. J. Pure Appl. Math., 2017. Vol. 117, No. 13. P. 135–143.
  5. Guo D., Zhan H., Wong M.D.F. On coloring rectangular and diagonal grid graphs for multiple patterning lithography. In: 23rd Asia and South Pacific Design Automation Conference. IEEE Xplore, 2018. P. 387–392. DOI: 10.1109/ASPDAC.2018.8297354
  6. Stiebitz M., Scheide D., Toft B., Favrholdt L.M. Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture. Hoboken, NJ: John Wiley & Sons Inc., 2012. 344 p.
  7. Yeh R.K. Labelling Graphs with a Condition at Distance Two. Ph. D. Thesis. Columbia, SC: University of South Carolina, 1990.




DOI: http://dx.doi.org/10.15826/umj.2022.1.003

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.