On the total vertex irregularity strength of trees. (English) Zbl 1208.05014

Summary: A vertex irregular total \(k\)-labelling \(\lambda :V(G) \cup E(G) \to \{1,2,\dots ,k\}\) of a graph \(G\) is a labelling of vertices and edges of \(G\) done in such a way that for any different vertices \(x\) and \(y\), their weights \(wt(x)\) and \(wt(y)\) are distinct. The weight \(wt(x)\) of a vertex \(x\) is the sum of the label of \(x\) and the labels of all edges incident with \(x\). The minimum \(k\) for which a graph \(G\) has a vertex irregular total \(k\)-labelling is called the total vertex irregularity strength of \(G\), denoted by tvs\((G)\). In this paper, we determine the total vertex irregularity strength of trees.


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


[1] Amar, D.; Togni, O., Irregularity strength of trees, Discrete math., 190, 15-38, (1998) · Zbl 0956.05092
[2] Anholcer, M.; Kalkowski, M.; Przybyło, J., A new upper bound for the total vertex irregularity strength of graphs, Discrete math., 309, 6316-6317, (2009) · Zbl 1210.05117
[3] M. Bača, S. Jendrol’, M. Miller, On total edge irregular labellings of trees (unpublished).
[4] Bača, M.; Jendrol’, S.; Miller, M.; Ryan, J., On irregular total labellings, Discrete math., 307, 1378-1388, (2007) · Zbl 1115.05079
[5] Bohman, T.; Kravitz, D., On the irregularity strength of trees, J. graph theory, 45, 4, 241-254, (2004) · Zbl 1034.05015
[6] Chartrand, G.; Jacobson, M.S.; Lehel, J.; Oellermann, O.R.; Ruiz, S.; Saba, F., Irregular networks, Congr. numer., 64, 187-192, (1988)
[7] Gallian, J.A., Graph labeling, Electron. J. combin. dyn. surv., DS6, (2007)
[8] Ivančo, J.; Jendrol’, S., Total edge irregularity strength of trees, Discuss. math. graph theory, 26, 449-456, (2006) · Zbl 1135.05066
[9] M.S. Jacobson, J. Lehel, Degree irregularity. Available online at: http://athena.luisville.edu/ msjaco01/irregbib.html.
[10] Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. discrete math., 13, 3, 313-323, (2000) · Zbl 0947.05067
[11] Nurdin; Baskoro, E.T.; Salman, A.N.M., The total edge irregular strengths of union graphs of \(K_{2, n}\), J. mat. sain, 11, 3, 105-109, (2006)
[12] Nurdin, E.T. Baskoro, A.N.M. Salman, N.N. Gaos, On total vertex-irregular labellings for several types of trees, Util. Math. (in press). · Zbl 1242.05242
[13] Nurdin; Salman, A.N.M.; Baskoro, E.T., The total edge-irregular strengths of the corona product of paths with some graphs, J. combin. math. combin. comput., 65, 163-175, (2008) · Zbl 1172.05033
[14] Wallis, W.D., Magic graphs, (2001), Birkhäuser Boston · Zbl 0979.05001
[15] Wijaya, K.; Slamin; Surahmat; Jendrol’, S., Total vertex irregular labeling of complete bipartite graphs, J. combin. math. combin. comput., 55, 129-136, (2005) · Zbl 1100.05090
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.