zbMATH — the first resource for mathematics

A new upper bound for the total vertex irregularity strength of graphs. (English) Zbl 1210.05117
Summary: We investigate the following modification of the well-known irregularity strength of graphs. Given a total weighting \(w\) of a graph \(G=(V,E)\) with elements of a set \(\{1,2,\dots ,s\}\), denote \(wt_G(v)=\sum _{e\ni v}w(e)+w(v)\) for each \(v\in V\). The smallest \(s\) for which exists such a weighting with \(wt_G(u)\neq wt_G(v)\) whenever \(u\) and \(v\) are distinct vertices of \(G\) is called the total vertex irregularity strength of this graph, and is denoted by tvs\((G)\). We prove that tvs\((G)\leq 3\lceil n/\delta \rceil\) for each graph of order \(n\) and with minimum degree \(\delta >0\).

05C75 Structural characterization of families of graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI
[1] Bača, M.; Jendroľ, S.; Miller, M.; Ryan, J., On irregular total labelings, Discrete math., 307, 1378-1388, (2007) · Zbl 1115.05079
[2] Chartrand, G.; Jacobson, M.S.; Lehel, J.; Oellermann, O.R.; Ruiz, S.; Saba, F., Irregular networks, Congr. numer., 64, 187-192, (1988)
[3] Faudree, R.J.; Lehel, J., Bound on the irregularity strength of regular graphs, (), 247-256 · Zbl 0697.05048
[4] Frieze, A.; Gould, R.J.; Karoński, M.; Pfender, F., On graph irregularity strength, J. graph theory, 41, 2, 120-137, (2002) · Zbl 1016.05045
[5] M. Kalkowski, A note on 1, 2-conjecture, Electron. J. Combin. (submitted for publication)
[6] Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. discrete math., 13, 3, 313-323, (2000) · Zbl 0947.05067
[7] Przybyło, J., Irregularity strength of regular graphs, Electron. J. combin., 15, 1, #R82, (2008) · Zbl 1163.05329
[8] Przybyło, J., Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. discrete math., 23, 1, 511-516, (2009) · Zbl 1216.05135
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.