| Title:
|
Edge-sum distinguishing labeling (English) |
| Author:
|
Bok, Jan |
| Author:
|
Jedličková, Nikola |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
62 |
| Issue:
|
2 |
| Year:
|
2021 |
| Pages:
|
135-149 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We study edge-sum distinguishing labeling, a type of labeling recently introduced by Z. Tuza (2017) in context of labeling games. An ESD labeling of an $n$-vertex graph $G$ is an injective mapping of integers $1$ to $l$ to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If $ l$ equals to $n$, we speak about a canonical ESD labeling. We focus primarily on structural properties of this labeling and show for several classes of graphs if they have or do not have a canonical ESD labeling. As an application we show some implications of these results for games based on ESD labeling. We also observe that ESD labeling is closely connected to the well-known notion of magic and antimagic labelings, to the Sidon sequences and to harmonious labelings. (English) |
| Keyword:
|
graph theory |
| Keyword:
|
graph labeling |
| Keyword:
|
games on graphs |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 07396214 |
| idMR:
|
MR4303573 |
| DOI:
|
10.14712/1213-7243.2021.010 |
| . |
| Date available:
|
2021-07-28T08:31:36Z |
| Last updated:
|
2023-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149006 |
| . |
| Reference:
|
[1] Bača M., Lin Y., Miller M., Youssef M. Z.: Edge-antimagic graphs.Discrete Math. 307 (2007), no. 11–12, 1232–1244. MR 2311093, 10.1016/j.disc.2005.10.038 |
| Reference:
|
[2] Gallian J. A.: A dynamic survey of graph labeling.Electron. J. Combin. 5 (1998), Dynamic Survay 6, 43 pages. MR 1668059 |
| Reference:
|
[3] Graham R. L., Sloane N. J. A.: On additive bases and harmonious graphs.SIAM J. Algebraic Discrete Methods 1 (1980), no. 4, 382–404. MR 0593849, 10.1137/0601045 |
| Reference:
|
[4] Guy R. K.: Unsolved Problems in Number Theory.Problem Books in Mathematics, Springer, New York, 2004. Zbl 1058.11001, MR 2076335 |
| Reference:
|
[5] Hale W. K.: Frequency assignment: Theory and applications.Proceedings of the IEEE 68 (1980), no. 12, 1497–1514. |
| Reference:
|
[6] Jha P. K.: Optimal ${L}(2, 1)$-labeling of Cartesian products of cycles, with an application to independent domination.IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 47 (2000), no. 10, 1531–1534. MR 1827298 |
| Reference:
|
[7] Kotzig A., Rosa A.: Magic valuations of finite graphs.Canad. Math. Bull. 13 (1970), no. 4, 451–461. MR 0272664, 10.4153/CMB-1970-084-1 |
| Reference:
|
[8] Kotzig A., Rosa A.: Magic Valuations of Complete Graphs.Centre de Recherches Mathématiques, Université de Montréal, 1972. MR 0272664 |
| Reference:
|
[9] O'Bryant K.: A complete annotated bibliography of work related to Sidon sequences.Electronic Journal of Combinatorics 1000 (2004), #DS11, 39 pages. 10.37236/32 |
| Reference:
|
[10] Rahmawati S., Sugeng K. A., Silaban D. R., Miller M., Bača M.: Construction of new larger $(a,d)$-edge antimagic vertex graphs by using adjacency matrices.Australas. J. Combin. 56 (2013), 257–272. MR 3097727 |
| Reference:
|
[11] Rosa A.: On certain valuations of the vertices of a graph.Theory of Graphs, Internat. Symp., Rome, 1966, Gordon and Breach, New York, 1967, 349–355. MR 0223271 |
| Reference:
|
[12] Sidon S.: Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen.Math. Ann. 106 (1932), no. 1, 536–539 (German). MR 1512772, 10.1007/BF01455900 |
| Reference:
|
[13] Simanjuntak R., Bertault F., Miller M.: Two new $(a,d)$-antimagic graph labelings.Proc. of Eleventh Australasian Workshop on Combinatorial Algorithms 11 (2000), pages 179–189. |
| Reference:
|
[14] Tuza Z.: Graph labeling games.Electron. Notes Discrete Math. 60 Elsevier Sci. B. V., Amsterdam (2017), 61–68. MR 3667978 |
| Reference:
|
[15] van den Heuvel J., Leese R. A., Shepherd M. A.: Graph labeling and radio channel assignment.J. Graph Theory 29 (1998), no. 4, 263–283. MR 1653829, 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V |
| Reference:
|
[16] Wallis W. D.: Magic Graphs.Birkhäuser Boston, Springer Science & Business Media, 2001. MR 1874683 |
| Reference:
|
[17] West D. B.: Introduction to Graph Theory.Prentice Hall Upper Saddle River, University of Illinois, Urbana-Champaign, 2001. Zbl 1121.05304, MR 1367739 |
| . |
