On irregular total labellings. (English) Zbl 1115.05079

Summary: Two new graph characteristics, the total vertex irregularity strength and the total edge irregularity strength, are introduced. Estimations on these parameters are obtained. For some families of graphs the precise values of these parameters are proved.


05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI Link


[1] Amar, D.; Togni, O., Irregularity strength of trees, Discrete math., 190, 15-38, (1998) · Zbl 0956.05092
[2] Chartrand, G.; Jacobson, M.S.; Lehel, J.; Oellermann, O.R.; Ruiz, S.; Saba, F., Irregular networks, Congr. numer., 64, 187-192, (1988)
[3] Dimitz, J.H.; Garnick, D.K.; Gyárfás, A., On the irregularity strength of the \(m \times n\) grid, J. graph theory, 16, 355-374, (1992) · Zbl 0771.05055
[4] Faudree, R.J.; Jacobson, M.S.; Lehel, J.; Schlep, R.H., Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete math., 76, 223-240, (1988) · Zbl 0685.05029
[5] R.J. Faudree, J. Lehel, Bounds on the irregularity strength of regular graphs, in: Combinatorics (Eger, (1987)) Colloquia Mathematica Societatis János Bobyai, vol. 52, North-Holland, Amsterdam, 1988, pp. 247-256.
[6] Gallian, J.A., Graph labeling, Electron. J. combin., 5, (1998), (Dynamic Survey DS6) · Zbl 0953.05067
[7] Gyárfás, A., The irregularity strength of \(K_{m, m}\) is 4 for odd m, Discrete math., 71, 273-274, (1998) · Zbl 0681.05066
[8] M.S. Jacobson, J. Lehel, Degree irregularity, available online at \(\langle\)http://athena.louisville.edu/msjaco01/irregbib.html⟩.
[9] Jendrol’, S.; Tkáč, M., The irregularity strength of \(\mathit{tK}_p\), Discrete math., 145, 301-305, (1995) · Zbl 0834.05029
[10] Jendrol’, S.; Tkáč, M.; Tuza, Z., The irregularity strength and cost of the union of cliques, Discrete math., 150, 179-186, (1996) · Zbl 0852.05054
[11] J. Lehel, Facts and quests on degree irregular assignment, Graph Theory, Combin. Appl., Wiley, New York, 1991, pp. 765-782.
[12] Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. discrete math., 13, 313-323, (2000) · Zbl 0947.05067
[13] Wallis, W.D., Magic graphs, (2001), Birkhäuser Boston · Zbl 0979.05001
[14] D.R. Wood, On pseudo vertex-magic and edge-magic total labelings, in: E.T. Baskoro (Ed.), Proceedings of the Twelfth Australasian Workshop on Combinatorial Algorithms, ITB Bandung, July 14-17, 2001, pp. 180-198.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.