Volume 16, Issue 1 (4-2021)                   IJMSI 2021, 16(1): 1-13 | Back to browse issues page

XML Print


Let $G=(V(G),E(G))$ be a simple, finite and undirected graph of order $n$. A $k$-vertex weightings of a graph $G$ is a mapping $w: V(G) to {1, ldots, k}$. A $k$-vertex weighting induces an edge labeling $f_w: E(G) to N$ such that $f_w(uv)=w(u)+w(v)$. Such a labeling is called an {it edge-coloring k-vertex weightings} if $f_{w}(e)not= f_{w}(echr(chr('39')39chr('39')))$ for any two adjacent edges $e$ and $echr(chr('39')39chr('39'))$. Denote by $muchr(chr('39')39chr('39'))(G)$ the minimum $k$ for $G$ to admit an edge-coloring $k$-vertex weightings. In this paper, we determine $muchr(chr('39')39chr('39'))(G)$ for some classes of graphs.

Type of Study: Research paper | Subject: Special

1. J.A. Bondy, U.S.R. Murty, Graph theory with applications, New York, MacMillan, 1976. [DOI:10.1007/978-1-349-03521-2]
2. G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex coloring edge-weighting of graphs, Taiwanese J. Math., 15(4), (2011) 1807-1813. [DOI:10.11650/twjm/1500406380]
3. M.R. Farahani, A new vertex-coloring edge-weighting of complete graphs, J. Appl. Math. & Informatics, Vol. 32, (2014), No. 1 - 2, 1 - 6. [DOI:10.14317/jami.2014.001]
4. J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Comb., 20, (2017) #DS6.
5. M. Kalkowski, M. Kar'onski, and F. Pfender, Vertax-Coloring Edge-weighting With Integer Weights At Most 6, Rostock. Math. Kolloq., 64, (2009), 39-43.
6. M. Kalkowski, M.Kar'onski, and F. Pfender, Vertex-coloring edge-weightings: Towards the 1-2-3-conjecture, J. Combin. Theory, Ser. B, 100, (2010), 347-349. [DOI:10.1016/j.jctb.2009.06.002]
7. M. Kar'onski, T. Luczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, (2004) 151¨C157. [DOI:10.1016/j.jctb.2003.12.001]
8. D. Leven and Z. Galil, NP completeness of finding the chromatic index of regular graphs, J. Algorithms, 4(1), (1983), 35 - 44. [DOI:10.1016/0196-6774(83)90032-9]
9. T. Wang, and Q. Yu, On vertex-coloring $13$-edge-weighting, Front. Math. China, 3(4), (2008), 1-7. [DOI:10.1007/s11464-008-0041-x]