Rainbow neighbourhood number of graphs

• Kok, Johan ^[2] ; Naduvath, Sudev ^[2] ; Jamil, Muhammad Kamran ^[1]
  1. [1] Riphah International University

     Riphah International University

     Pakistán

     
  2. [2] CHRIST (Deemed to be University).
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 38, Nº. 3, 2019, págs. 469-484
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-2019-03-0030
• Enlaces
  • Texto completo
• Resumen

  • In this paper, we introduce the notion of the rainbow neighbourhood and a related graph parameter namely the rainbow neighbourhood number and report on preliminary results thereof. The closed neighbourhood N [v] of a vertex v ∈ V (G) which contains at least one coloured vertex of each colour in the chromatic colouring of a graph is called a rainbow neighbourhood. The number of rainbow neighbourhoods in a graph G is called the rainbow neighbourhood number of G, denoted by rχ(G). We also introduce the concepts of an expanded line graph of a graph G and a v-clique of v ∈ V (G). With the help of these new concepts, we also establish a necessary and sufficient condition for the existence of a rainbow neighbourhood in the line graph of a graph G.

• Referencias bibliográficas
  • B. Andrásfai, P. Erdös, and V. Sós, “On the connection between chromatic number, maximal clique and minimal degree of a graph”, Discrete Mathematics,...
  • J. Bondy and U. Murty, Graph theory, Elsevier Science: New York, 1976.
  • R. Brooks, “On colouring the nodes of a network”, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, no. 2, pp. 194–197,...
  • G. Chartrand and L. Lesniak, Graphs & digraphs. Boca Raton, FL: Chapman & Hall/CRC, 2000.
  • G. Chartrand and P. Zhang, Chromatic graph theory. (Discrete Mathematics and Its Applications) Boca Raton, FL: CRC Press, 2009.
  • R. Green, “Vizing’s theorem and edge-chromatic graph theory”, 2015. [On line]. Available: http://bit.ly/2LZMCwg
  • F. Harary, Graph theory, 5th ed. New Delhi: Narosa Publishing House, 2001.
  • T. Jensen and B. Toft, Graph coloring problems. New York, NY: John Wiley & Sons, Inc., 1995, doi: 10.1002/9781118032497.
  • S. Kalayathankal and C. Susanth, “The sum and product of chromatic numbers of graphs and their line graphs”, Journal Of Informatics And Mathematical...
  • A. King, B. Reed, and A. Vetta, “An upper bound for the chromatic number of line graphs”, European Journal of Combinatorics, vol. 28, no....
  • J. Kok, N. Sudev, and K. Chithra, “Generalised colouring sums of graphs”, Cogent Mathematics, vol. 3, no. 1, Feb. 2016, doi: 10.1080/23311835.2016.1140002.
  • J. Kok and N. Sudev, “Theb-chromatic number of certain graphs and digraphs”, Journal of Discrete Mathematical Sciences and Cryptography, vol....
  • M. Kubale, Ed., Graph colorings (Contemporary Mathematics, vol. 352). Providence, RI: American Mathematical Society, Jun. 2004, doi: 10.1090/conm/352.
  • D. West, Introduction to graph theory, 2nd ed. Dehli: Pearson Education Inc., 2001.