Edge-sum distinguishing labeling

Jan Bok; Nikola Jedličková

Commentationes Mathematicae Universitatis Carolinae (2021)

  • Issue: 2, page 135-149
  • ISSN: 0010-2628

Abstract

top
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.

How to cite

top

Bok, Jan, and Jedličková, Nikola. "Edge-sum distinguishing labeling." Commentationes Mathematicae Universitatis Carolinae (2021): 135-149. <http://eudml.org/doc/298072>.

@article{Bok2021,
abstract = {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.},
author = {Bok, Jan, Jedličková, Nikola},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph theory; graph labeling; games on graphs},
language = {eng},
number = {2},
pages = {135-149},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Edge-sum distinguishing labeling},
url = {http://eudml.org/doc/298072},
year = {2021},
}

TY - JOUR
AU - Bok, Jan
AU - Jedličková, Nikola
TI - Edge-sum distinguishing labeling
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2021
PB - Charles University in Prague, Faculty of Mathematics and Physics
IS - 2
SP - 135
EP - 149
AB - 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.
LA - eng
KW - graph theory; graph labeling; games on graphs
UR - http://eudml.org/doc/298072
ER -

References

top
  1. Bača M., Lin Y., Miller M., Youssef M. Z., 10.1016/j.disc.2005.10.038, Discrete Math. 307 (2007), no. 11–12, 1232–1244. MR2311093DOI10.1016/j.disc.2005.10.038
  2. Gallian J. A., A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998), Dynamic Survay 6, 43 pages. MR1668059
  3. Graham R. L., Sloane N. J. A., 10.1137/0601045, SIAM J. Algebraic Discrete Methods 1 (1980), no. 4, 382–404. MR0593849DOI10.1137/0601045
  4. Guy R. K., Unsolved Problems in Number Theory, Problem Books in Mathematics, Springer, New York, 2004. Zbl1058.11001MR2076335
  5. Hale W. K., Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980), no. 12, 1497–1514. 
  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. MR1827298
  7. Kotzig A., Rosa A., 10.4153/CMB-1970-084-1, Canad. Math. Bull. 13 (1970), no. 4, 451–461. MR0272664DOI10.4153/CMB-1970-084-1
  8. Kotzig A., Rosa A., Magic Valuations of Complete Graphs, Centre de Recherches Mathématiques, Université de Montréal, 1972. MR0272664
  9. O'Bryant K., 10.37236/32, Electronic Journal of Combinatorics 1000 (2004), #DS11, 39 pages. DOI10.37236/32
  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. MR3097727
  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. MR0223271
  12. Sidon S., 10.1007/BF01455900, Math. Ann. 106 (1932), no. 1, 536–539 (German). MR1512772DOI10.1007/BF01455900
  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. 
  14. Tuza Z., Graph labeling games, Electron. Notes Discrete Math. 60 Elsevier Sci. B. V., Amsterdam (2017), 61–68. MR3667978
  15. van den Heuvel J., Leese R. A., Shepherd M. A., 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V, J. Graph Theory 29 (1998), no. 4, 263–283. MR1653829DOI10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V
  16. Wallis W. D., Magic Graphs, Birkhäuser Boston, Springer Science & Business Media, 2001. MR1874683
  17. West D. B., Introduction to Graph Theory, Prentice Hall Upper Saddle River, University of Illinois, Urbana-Champaign, 2001. Zbl1121.05304MR1367739

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.