Silver graphs
Yükleniyor...
Dosyalar
Tarih
2009
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Maltepe Üniversitesi
Erişim Hakkı
CC0 1.0 Universal
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Özet
A problem was given in the International Mathematical Olympiad in 1997 (IMO97–Problem 4) on “silver matrices”. It
came from a research problem in graph colorings called defining sets and in latin squares critical sets, Mahdian and Mahmoodian
[2]. In a given graph G, a set of vertices S with an assignment of colors is called a defining set of the (proper) k–coloring if there
exists a unique extension of the colors of S to a k–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, k). Existence of a silver matrix
of order n is equivalent to d(Kn¤Kn, 2n − 1) = n
2 − n. Recently we have studied silver d–cubes [1], that is when we have
d(
d
z }| {
Kn¤Kn¤ · · · ¤Kn, dn − d + 1) = n
d − n
d−1
. Silver d–cubes are attractive, challenging to construct, and appear to be
connected with classical combinatorics, including coding theory and projective geometry.
In general a silver graph is defined as follows. Let c be a proper (r + 1)-coloring of an r-regular graph G. A vertex x
in G is said to be rainbow with respect to c if every color appears in the closed neighborhood N[x] = N(x) ∪ {x}. Given a
maximum independent set I of G, the coloring c is said to be silver with respect to I if every x ∈ I is rainbow with respect to
c. We say G is silver if it admits a silver coloring with respect to some diagonal. If all vertices of G are rainbow, then c is
called a totally silver coloring of G and G is said to be totally silver. In this talk we will discuss silver graphs and its relation
with some concepts in combinatorics and graph theory and at the end some unsolved problems will be stated.
Açıklama
Anahtar Kelimeler
Künye
Mahmoodian, B. S. (2009). Silver graphs. Maltepe Üniversitesi. s. 144.
