Volume 16, Issue 1 (4-2021)
IJMSI 2021, 16(1): 1-13 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Shiu W, Lau G, Ng H. Edge-coloring Vertex-weightings of Graphs. IJMSI 2021; 16 (1) :1-13
URL: http://ijmsi.ir/article-1-1033-en.html
URL: http://ijmsi.ir/article-1-1033-en.html
Abstract:
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}(e')$ for any two adjacent edges $e$ and $e'$. Denote by $mu'(G)$ the minimum $k$ for $G$ to admit an edge-coloring $k$-vertex weightings. In this paper, we determine $mu'(G)$ for some classes of graphs.
Keywords: Edge coloring, Vertex weightings.
Type of Study: Research paper |
Subject:
Special
References
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]
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
