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

D. Ali Mojdeh

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 59-72
  • ISSN: 2083-5892

Abstract

top
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 ₃ × C 2 r , 4 ) , which is given an upper and lower bounds for this defining number. Also some bounds of defining number are introduced.

How to cite

top

D. Ali Mojdeh. "Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph." Discussiones Mathematicae Graph Theory 26.1 (2006): 59-72. <http://eudml.org/doc/270621>.

@article{D2006,
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₃×C_\{2r\},4)$, which is given an upper and lower bounds for this defining number. Also some bounds of defining number are introduced.},
author = {D. Ali Mojdeh},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph coloring; defining set; cartesian product},
language = {eng},
number = {1},
pages = {59-72},
title = {Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph},
url = {http://eudml.org/doc/270621},
volume = {26},
year = {2006},
}

TY - JOUR
AU - D. Ali Mojdeh
TI - Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 59
EP - 72
AB - 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₃×C_{2r},4)$, which is given an upper and lower bounds for this defining number. Also some bounds of defining number are introduced.
LA - eng
KW - graph coloring; defining set; cartesian product
UR - http://eudml.org/doc/270621
ER -

References

top
  1. [1] J. Cooper, D. Donovan and J. Seberry, Latin squares and critical sets of minimal size, Austral. J. Combin. 4 (1991) 113-120. Zbl0759.05017
  2. [2] M. Mahdian and E.S. Mahmoodian, A characterization of uniquely 2-list colorable graph, Ars Combin. 51 (1999) 295-305. Zbl0977.05046
  3. [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. [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. Zbl0924.05025
  5. [5] E.S. Mahmoodian, R. Naserasr and M. Zaker, Defining sets in vertex colorings of graphs and Latin rectangles, Discrete Math. (to appear). Zbl0879.05028
  6. [6] E. Mendelsohn and D.A. Mojdeh, On defining spectrum of regular graph, (submitted). Zbl1227.05148
  7. [7] D.A. Mojdeh, On conjectures of the defining set of (vertex) graph colourings, Austral. J. Combin. (to appear). Zbl1107.05035
  8. [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. Zbl0837.05017
  9. [9] D.B. West, Introduction to Graph Theory (Second Edition) (Prentice Hall, USA, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.