1. bookVolume 27 (2019): Issue 1 (June 2019)
Journal Details
License
Format
Journal
First Published
30 Jul 2019
Publication timeframe
2 times per year
Languages
English
access type Open Access

On Neighbor chromatic number of grid and torus graphs

Published Online: 21 Dec 2019
Page range: 3 - 15
Received: 25 Apr 2018
Accepted: 17 Jun 2018
Journal Details
License
Format
Journal
First Published
30 Jul 2019
Publication timeframe
2 times per year
Languages
English
Abstract

A set SV is a neighborhood set of a graph G = (V, E), if G = ∪v∈SN[v] 〉, where 〈 N[v] 〉 is the subgraph of a graph G induced by v and all vertices adjacent to v. A neighborhood set S is said to be a neighbor coloring set if it contains at least one vertex from each color class of a graph G, where color class of a colored graph is the set of vertices having one particular color. The neighbor chromatic number χn (G) is the minimum cardinality of a neighbor coloring set of a graph G. In this article, some results on neighbor chromatic number of Cartesian products of two paths (grid graph) and cycles (torus graphs) are explored.

Keywords

MSC 2010

[1] B. Chaluvaraju, Some parameters on neighborhood number of a graph. Electronic Notes of Discrete Mathematics, Elsevier, vol. 33, 2009, 139-146.Search in Google Scholar

[2] B. Chaluvaraju, C. N. Kumar, C. Appajigowda, The neighbor coloring sets in graphs, International J. of Applied Math. and Computation, vol. 4, no. 3, 2012, 307-311.Search in Google Scholar

[3] T. Y. Chang, Domination numbers of grid graphs, Ph.D. Thesis, Department of Mathematics, University of South Florida, 1992.Search in Google Scholar

[4] F. Harary, Graph theory, Addison-Wesley, Reading Mass, 1969.Search in Google Scholar

[5] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekkar, Inc., 1997.Search in Google Scholar

[6] W. Imrich, S. Klavzar, Product Graphs; Structure and Recognition, John Wiley and Sons, New York., 2000.Search in Google Scholar

[7] W. Imrich, S. Klavzar, D. F. Rall, Topics in Graph Theory: Graphs and their Cartesian product, A. K. Peters, Ltd., Wellesley, 2008.Search in Google Scholar

[8] M. S. Jacobson, L. F. Kinch, On the domination number of products of a graph; I, Ars Comb., vol. 10, 1983, 33-44.Search in Google Scholar

[9] T. R. Jensen, B. Toft, Graph Coloring Problem, John Wiley & Sons, Inc, New York, 1995.Search in Google Scholar

[10] S. Klavzar, N. Seifter, Dominating Cartesian products of cycles, Discrete Applied Mathematics, vol. 59, 1995, 129-136.Search in Google Scholar

[11] R. H. Lamprey, B. H. Barnes, Product graphs and their applications, Modelling and Simulation, Proc. Fifth Annual Pittsburgh Conference, Instrument Society of America, Pittsburgh, PA., vol. 5, 1974, 1119-1123.Search in Google Scholar

[12] V. R. Kulli, S. C. Sigarkanti, Further results on the neighborhood number of graphs. Indian J. Pure Appl. Math, vol. 23, no. 8, 1992, 575-577.Search in Google Scholar

[13] R. Gera, On Dominator colorings in graphs, Graph Theory Notes of New York LII, 2007, 25-30.Search in Google Scholar

[14] R. Hammack, W. Imrich, S. Klavzar, Hand book of product graph. CRC press, Taylor & Francis group, LLC, 2011.Search in Google Scholar

[15] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math., vol. 9, 1957, 515-525.Search in Google Scholar

[16] E. Sampathkumar, P. S. Neeralagi, The neighborhood number of a graph, Indian J. Pure and Appl. Math., vol. 16, no. 2, 1985, 126-132.Search in Google Scholar

[17] Y. B. Venkatakrishnan, V. Swaminathan, Colour class domination numbers of some classes of graphs, Algebra and Discrete Mathematics, vol. 18, no. 2, 2014, 301-305.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo