Skip to main content
SUPERVISOR
Behnaz Omoomi,Gholamreza Omidi
بهناز عمومی (استاد راهنما) غلامرضا امیدی اردلی (استاد مشاور)
 
STUDENT
Ali Behtoei
علی بهتوئی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Doctor of Philosophy (PhD)
YEAR
1386

TITLE

The Locating Coloring of Graphs
Let $c$ be a proper $k$-coloring of a connected graph $G$ and $Pi:=(V_1,V_2,ldots,V_k)$ be an ordered partition of $V(G)$ into the resulting color code of $v$ with respect to $Pi$ is defined to be the ordered $k$-tuple $ $c_{{}_Pi}(v):=(d(v,V_1),d(v,V_2),ldots,d(v,V_k)), $ $ where $d(v,V_i)=min{d(v,x)~|~xin V_i}, 1leq ileq k$. If distinct vertices have distinct color codes, then $c$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by $Cchi_{{}_L}(G)$. %%%%% In this thesis, we study the locating chromatic number of Kneser graphs, Cartesian product of graphs, and the join of graphs. First, among some other results we show that $Cchi_{{}_L}(KG(n,2))=n-1$ for all $ngeq 5$. Then, we prove that $Cchi_{{}_L}(KG(n,k))leq n-1$, when $ngeq k^2$. Moreover, we present some bounds for the locating chromatic number of odd graphs, which shows the difference between the chromatic number and the locating chromatic number of these graphs can be arbitrary far apart. %%%%% Also, we determine the locating chromatic number of the grids and the Cartesian product of paths and complete graphs. For the Cartesian product of two complete graphs, we compute the exact value of the locating chromatic number in some cases, and we offer conjectures for the remaining cases. %%%%% In order to study the locating chromatic number of the join of graphs, we define a new parameter which is closely related to the locating chromatic number. Then, using this parameter, we determine the exact value of the locating chromatic number of the join of paths, cycles and complete multipartite graphs.
فرض کنید $c$ یک $k$- رنگ‌آمیزی معتبر از گراف همبند $G$ با کلاس‌های رنگی $V_1$ ، $V_2$ ، $\ldots$ ، $V_k$ باشد. $\Pi:=(V_1,V_2,...,V_k)$ را افراز مرتب حاصل از این رنگ‌آمیزی در نظر بگیرید. کد رنگی رأس $v\in V(G)$ یک $k$ -تائی مرتب است که به صورت زیر تعریف می‌شود \vspace*{3mm} $$ c_{{}_\Pi}(v) :=(d(v,V_1),d(v,V_2),\ldots,d(v,V_k)).$$ اگر رئوس متمایز $G$ کدهای رنگی متمایز داشته باشند ، آن‌گاه $c$ یک $k $ -رنگ‌آمیزی مکان‌یاب نامیده می‌شود. کوچک‌ترین عدد صحیح $k$ با این خاصیت را عدد رنگی مکان‌یاب $ G $ ، $ \Cchi_{{}_L}(G) $ ، می‌نامند. در این رساله عدد رنگی مکان‌یاب را برای گراف‌های کنسر ، حاصل‌ضرب دکارتی گراف‌ها، و الحاق گراف‌ها مورد مطالعه و بررسی قرار می‌دهیم. ابتدا ثابت می‌کنیم که برای هر $ n\geq5 $ مقدار دقیق عدد رنگی مکان‌یاب $KG(n,2)$ برابر $n-1$ است. در حالت $k\geq 3$ نشان می‌دهیم که اگر $n\geq k^2$ ، آن‌گاه عدد رنگی مکان‌یاب $ KG(n,k) $ حداکثر $n-1$ است. سپس ، با ارائه کران‌هایی برای عدد رنگی مکان‌یاب گراف‌های فرد ، نشان می‌دهیم که فاصله‌ی بین عدد رنگی و عدد رنگی مکان‌یاب گراف‌های فرد را به هر میزان دل‌خواهی می‌توان بزرگ کرد. هم‌چنین ، عدد رنگی مکان‌یاب حاصل‌ضرب دکارتی دو مسیر و حاصل‌ضرب دکارتی یک مسیر با یک گراف کامل را به طور دقیق محاسبه می‌کنیم. عدد رنگی مکان‌یاب حاصل‌ضرب دکارتی دو گراف کامل را نیز در برخی از حالت‌ها مشخص ، و برای بقیه‌ی حالت‌ها حدس‌هایی ارائه می‌کنیم. برای بررسی عدد رنگی مکان‌یاب الحاق گراف‌ها ، یک پارامتر جدید تعریف می‌کنیم که ارتباط بسیار نزدیکی با عدد رنگی مکان‌یاب دارد. سپس ، با استفاده از این پارامتر جدید مقدار دقیق عدد رنگی مکان‌یاب الحاق مسیرها ، دورها ، و گراف‌های چندبخشی کامل را به دست می‌آوریم.

ارتقاء امنیت وب با وف بومی