×

Total edge irregularity strength of complete graphs and complete bipartite graphs. (English) Zbl 1291.05175

Hliněný, Petr (ed.) et al., 6th Czech-Slovak international symposium on combinatorics, graph theory, algorithms and applications, DIMATIA Center, Charles University, Prague, Czech Republic, July 10–16, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 28, 281-285 (2007).
Summary: A total edge irregular \(k\)-labelling \(\nu\) of a graph \(G\) is a labelling of the vertices and edges of \(G\) with labels from the set \(\{1,\dots ,k\}\) in such a way that for any two different edges \(e\) and \(f\) their weights \(\varphi (f)\) and \(\varphi (e)\) are distinct where the weight of an edge \(g=uv\) is \(\varphi (g)=\nu (e)+\nu (u)+\nu (v)\), i.e. the sum of the label of \(g\) and the labels of vertices \(u\) and \(v\). The minimum \(k\) for which the graph \(G\) has an edge irregular total \(k\)-labelling is called the total edge irregularity strength of \(G\). We show the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.
For the entire collection see [Zbl 1109.05007].

MSC:

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

References:

[1] Amar, D.; Togni, O., Irregularity strength of trees, Discrete Math., 190, 15-38 (1998) · Zbl 0956.05092
[2] M. Bača, S. Jendrol’, M. Miller, J. Ryan : On irregular labellings, Discrete Math; M. Bača, S. Jendrol’, M. Miller, J. Ryan : On irregular labellings, Discrete Math
[3] Chartrand, G.; Jacobson, M. S.; Lehel, J.; Oellermann, O. R.; Ruiz, S.; Saba, F., Irregurar networks, Congr. Numer., 64, 355-374 (1988)
[4] Dinitz, 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
[5] Frieze, A.; Gould, R. J.; Karonski, M.; Pfender, F., On graph irregularity strength, J. Graph Theory, 41, 120-137 (2004) · Zbl 1016.05045
[6] J. Ivančo, S. Jendrol’ : The total edge irregularity strength of trees, Discuss. Math. Graph Theory; J. Ivančo, S. Jendrol’ : The total edge irregularity strength of trees, Discuss. Math. Graph Theory
[7] Jacobson, M. S.; Lehel, J., Degree irregularity, Available online at · Zbl 0755.05092
[8] Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math., 13, 313-323 (2000) · Zbl 0947.05067
[9] Togni, O., Irregularity strength of the toroidal grid, Discrete Math., 165/166, 609-620 (1997) · Zbl 0883.05083
[10] Wallis, W. D., Magic Graphs (2001), Birkhäuser: Birkhäuser Boston · Zbl 0979.05001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.