Edge colouring by total labellings |
| |
Authors: | Stephan Brandt Michael Stiebitz |
| |
Institution: | a Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany b Institute of Mathematics, Faculty of Science, University of Pavol Jozef Šafarik, 040 01 Košice, Slovak Republic |
| |
Abstract: | We introduce the concept of an edge-colouring total k-labelling. This is a labelling of the vertices and the edges of a graph G with labels 1,2,…,k such that the weights of the edges define a proper edge colouring of G. Here the weight of an edge is the sum of its label and the labels of its two endvertices. We define to be the smallest integer k for which G has an edge-colouring total k-labelling. This parameter has natural upper and lower bounds in terms of the maximum degree Δ of . We improve the upper bound by 1 for every graph and prove . Moreover, we investigate some special classes of graphs. |
| |
Keywords: | Edge colouring Total labelling Irregularity strength Discrepancy |
本文献已被 ScienceDirect 等数据库收录! |
|