PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

Discussiones Mathematicae Graph Theory

2006 | 26 | 1 | 59-72
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
59-72
Opis fizyczny
Daty
wydano
2006
otrzymano
2004-11-06
poprawiono
2005-09-13
Twórcy
autor
• Department of Mathematics, University of Mazandaran, Babolsar, IRAN, P.O. Box 47416-1467
Bibliografia
• [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).
Typ dokumentu
Bibliografia
Identyfikatory