Total edge irregularity strength of trees

Jaroslav Ivančo; Stanislav Jendrol'

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 3, page 449-456
  • ISSN: 2083-5892

Abstract

top
A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every tree T of maximum degree Δ on p vertices tes(T) = max{⎡(p+1)/3⎤,⎡(Δ+1)/2⎤}.

How to cite

top

Jaroslav Ivančo, and Stanislav Jendrol'. "Total edge irregularity strength of trees." Discussiones Mathematicae Graph Theory 26.3 (2006): 449-456. <http://eudml.org/doc/270466>.

@article{JaroslavIvančo2006,
abstract = { A total edge-irregular k-labelling ξ:V(G)∪ E(G) → \{1,2,...,k\} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every tree T of maximum degree Δ on p vertices tes(T) = max\{⎡(p+1)/3⎤,⎡(Δ+1)/2⎤\}. },
author = {Jaroslav Ivančo, Stanislav Jendrol'},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph labelling; tree; irregularity strength; total labellings; total edge irregularity strength},
language = {eng},
number = {3},
pages = {449-456},
title = {Total edge irregularity strength of trees},
url = {http://eudml.org/doc/270466},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Jaroslav Ivančo
AU - Stanislav Jendrol'
TI - Total edge irregularity strength of trees
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 3
SP - 449
EP - 456
AB - A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every tree T of maximum degree Δ on p vertices tes(T) = max{⎡(p+1)/3⎤,⎡(Δ+1)/2⎤}.
LA - eng
KW - graph labelling; tree; irregularity strength; total labellings; total edge irregularity strength
UR - http://eudml.org/doc/270466
ER -

References

top
  1. [1] M. Aigner and E. Triesch, Irregular assignment of trees and forests, SIAM J. Discrete Math. 3 (1990) 439-449, doi: 10.1137/0403038. Zbl0735.05049
  2. [2] D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998) 15-38, doi: 10.1016/S0012-365X(98)00112-5. Zbl0956.05092
  3. [3] M. Bača, S. Jendrol' and M. Miller, On total edge irregular labelling of trees, (submitted). 
  4. [4] M. Bača, S. Jendrol', M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007) 1378–1388, doi: 10.1016/j.disc.2005.11.075. Zbl1115.05079
  5. [5] T. Bohman and D. Kravitz, On the irregularity strength of trees, J. Graph Theory 45 (2004) 241-254, doi: 10.1002/jgt.10158. Zbl1034.05015
  6. [6] L.A. Cammack, R.H. Schelp and G.C. Schrag, Irregularity strength of full d-ary trees, Congr. Numer. 81 (1991) 113-119. Zbl0765.05037
  7. [7] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 187-192. 
  8. [8] A. Frieze, R.J. Gould, M. Karoński and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002) 120-137, doi: 10.1002/jgt.10056. Zbl1016.05045
  9. [9] J.A. Gallian, Graph labeling, The Electronic Jounal of Combinatorics, Dynamic Survey DS6 (October 19, 2003). 
  10. [10] J. Lehel, Facts and quests on degree irregular assignment, in: Graph Theory, Combin. Appl. vol. 2, Y. Alavi, G. Chartrand, O.R. Oellermann and A.J. Schwenk, eds., (John Wiley and Sons, Inc., 1991) 765-782. Zbl0841.05052
  11. [11] T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000) 313-323, doi: 10.1137/S0895480196314291. Zbl0947.05067
  12. [12] W. D. Wallis, Magic Graphs (Birkhäuser Boston, 2001), doi: 10.1007/978-1-4612-0123-6. Zbl0979.05001

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.