ArticleOriginal scientific text

Title

Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph

Authors 1

Affiliations

  1. Department of Mathematics, University of Mazandaran, Babolsar, IRAN, P.O. Box 47416-1467

Abstract

In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c). The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G = Cₘ × Kₙ, c) with c > χ(G), where n ≥ 2 and m ≥ 3, unless the defining number d(K×C2r,4), which is given an upper and lower bounds for this defining number. Also some bounds of defining number are introduced.

Keywords

graph coloring, defining set, cartesian product

Bibliography

  1. J. Cooper, D. Donovan and J. Seberry, Latin squares and critical sets of minimal size, Austral. J. Combin. 4 (1991) 113-120.
  2. M. Mahdian and E.S. Mahmoodian, A characterization of uniquely 2-list colorable graph, Ars Combin. 51 (1999) 295-305.
  3. M. Mahdian, E.S. Mahmoodian, R. Naserasr and F. Harary, On defining sets of vertex colorings of the cartesian product of a cycle with a complete graph, Combinatorics, Graph Theory and Algorithms (1999) 461-467.
  4. E.S. Mahmoodian and E. Mendelsohn, On defining numbers of vertex coloring of regular graphs, 16th British Combinatorial Conference (London, 1997). Discrete Math. 197/198 (1999) 543-554.
  5. E.S. Mahmoodian, R. Naserasr and M. Zaker, Defining sets in vertex colorings of graphs and Latin rectangles, Discrete Math. (to appear).
  6. E. Mendelsohn and D.A. Mojdeh, On defining spectrum of regular graph, (submitted).
  7. D.A. Mojdeh, On conjectures of the defining set of (vertex) graph colourings, Austral. J. Combin. (to appear).
  8. A.P. Street, Defining sets for block designs; an update, in: C.J. Colbourn, E.S. Mahmoodian (eds), Combinatorics advances, Mathematics and its applications (Kluwer Academic Publishers, Dordrecht, 1995) 307-320.
  9. D.B. West, Introduction to Graph Theory (Second Edition) (Prentice Hall, USA, 2001).
Pages:
59-72
Main language of publication
English
Received
2004-11-06
Accepted
2005-09-13
Published
2006
Exact and natural sciences