Bilangan Kromatik Titik dari Dual Graf Berlian

Nurul Hafidhoh Anwar, Mohammad Nafie Jauhari, Dewi Ismiarti

Abstract


A vertex coloring of a graph , is an assigments of colors to the vertices of , such that no two adjacent vertices are assigned the same color. The least number of colors needed for an vertices coloring of a graph  is the chromatic number, denoted by . A graph is said to be planar if it can be drawn in the plane so that no edges crossing except at endpoints. A dual graph is constructed from the planar graph. Each region in planar graph can be represented by a vertex of the dual graph. Two vertices are connected if the region represented by these vertices are neugbours and have a common border. A diamond graph denoted by , can be used to model structure networks. In this study, it is shown that the chromatic number of dual diamond graph is  χ(〖Br_n〗^* )={█(3,&n=2 and n≥4@4,&n=3.)┤


Keywords


Vertex Coloring; Chromatic Number; Dual Graph; Diamond Graph

Full Text:

PDF

References


K. H. Rosen, "Discrete Mathematics and Its Applications (7th ed)," The McGraw-Hill Companies , United States, 2012.

J. A. Bondy and U. S. R. Murty, "Graduate Texts in Mathematics: Graph Theory," Springer, 2008.

R. J. Wilson and J. J. Watkins, "Graph An Introductory Approach. Terjemahan: Theresia M.H Tirta," IKIP Surabaya University Press 376 hal, Surabaya , 1990.

S. Lipschutz and M. L. Lipson, "Theory and Problems of Discrete Mathematics (3rd ed)," McGraw-Hill, United States, 2007.

I. K. Budayasa, "Teori Graf & Aplikasinya," Unesa University Press, Surabaya, 2007.

R. J. Wilson, "Introduction to Graph Theory (4th ed)," Addison Wasley Longman Limited, England, 1996.

M. R. Syafnur, L. Yulianti and D. Welyyanti, "Penentuan Bilangan Kromatik Lokasi untuk Graf Berlian Brn untuk n=3 dan n=4, VII(2)," 105-111, 2018.

G. Chartrand, L. Lesniak and P. Zhang, "Graphs & Digraphs (6th ed)," Chapman & Hall/RC, Boca Raton, 2016.

J. L. Gross, J. Yellen and M. Anderson, "Graph Theory and Its Applications (3rd ed)," Chapman & Hall/ CRC, Boca Raton, 2019.

M. Javedankherad, Z. Zeinalpour-Yazdi and F. Ashtiani, "Content Placement in Cache Networks Using Graph-Coloring," IEEE Systems Journal, vol. 14, no. 3, pp. 3129-3138, 2017.

N. Hinding, D. Firmayasari, H. Basir, M. Bača and A. Semaničová-Feňovčíková, "On Irregularity Strength of Diamond Network," AKCE International Journal of Graphs and Combinatorics, vol. 15, no. 3, pp. 291-297, 2018.




DOI: https://doi.org/10.18860/jrmm.v1i6.14517

Refbacks

  • There are currently no refbacks.