Title of article :
Edge-Coloring Vertex-Weighting of Graphs
Author/Authors :
Shiu, Wai-Chee College of Global Talents - Bejing Institute of Technology - Zhuhai, China - Department of Mathematics - The Chinese University of Hong Kong - Shatin, Hong Kong , Lau, Gee - Choon Faculty of Computer & Mathematical Sciences - Universiti Teknologi MARA Johor 85000 Segamat - Malaysia , Ng, Ho-Kuen Department of Mathematics - San José State University - San José CA 95192, USA
Abstract :
Let G = (V (G),E(G)) be a simple, finite and undirected graph of order n. A k-vertex weighting of a graph G is a mapping w : V (G) → {1, . . . , k}. A k-vertex weighting induces an edge labeling
fw : E(G) → N such that fw(uv) = w(u) + w(v). Such a labeling is
called an edge-coloring k-vertex weighting if fw(e) ̸= fw(e′) for any two
adjacent edges e and e′. Denote by μ′(G) the minimum k for G to admit
an edge-coloring k-vertex weighting. In this paper, we determine μ′(G) for some classes of graphs.
Farsi abstract :
فرض كنيد 𝐺=(𝑉(𝐺),𝐸(𝐺)) يك گراف بدون جهت، ساده و متناهي از مزتبه 𝑛 باشد. نگاشت 𝑤:𝑉(𝐺)→{1,2,…𝑘} يك k - راس وزن دهي از گراف G، ناميده مي شود. هر k -راس وزن دهي يك برچسب گذاري يال به صورت 𝑓𝑤:𝐸(𝐺)→𝑁 است به طوريكه 𝑓𝑤(𝑢𝑣)=𝑤(𝑢)+𝑤(𝑣). چنين برچسب گذاري را يك k -راس وزن دهي يال رنگي مي نامند اگر براي هر دو يال مجاور e و 𝑒′ ، 𝑓𝑤(𝑒)=𝑓𝑤(𝑒′). كمترين k اي كه براي گراف G بتوانيم يك k - راس وزن دهي يال رنگي داشته باشيم را 𝜇′(𝐺)
گوييم. در اين مقاله براي برخي رده ها از گراف ها 𝜇′(𝐺) را مشخص مي كنيم.
Keywords :
Edge coloring , Vertex weighting , Graphs
Journal title :
Iranian Journal of Mathematical Sciences and Informatics (IJMSI)
