Total edge irregularity strength of complete graphs and complete bipartite graphs

被引：82

作者：

Jendrol', Stanislav ^{[1
]}

Miskuf, Jozef ^{[1
]}

Sotak, Roman ^{[1
]}

机构：

[1] Univ Pavol Jozef Safarik, Fac Sci, Inst Math, Kosice, Slovakia

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 03期

关键词：

Irregular labelling; Total labelling; Complete graphs; Complete bipartite graphs; Irregularity strength;

D O I：

10.1016/j.disc.2009.03.006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A total edge irregular k-labelling v of a graph G is a labelling of the vertices and edges of G with labels from the set (1, ... , k) in such a way that for any two different edges e and f their weights phi(f) and phi(e) are distinct. Here, the weight of an edge g = uv is phi(g) = nu(g) + 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 have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：400 / 407

页数：8

共 12 条

[1] Irregularity strength of trees [J].

Amar, D ;

Togni, O .

DISCRETE MATHEMATICS, 1998, 190 (1-3) :15-38

[2] On irregular total labellings [J].

Baca, Martin ;

Jendrol, Stanislav ;

Miller, Mirka ;

Ryan, Joseph .

DISCRETE MATHEMATICS, 2007, 307 (11-12) :1378-1388

[3]

Chartrand G., 1988, C NUMER, V64, P355

[4] ON THE IRREGULARITY STRENGTH OF THE M X N GRID [J].

DINITZ, JH ;

GARNICK, DK ;

GYARFAS, A .

JOURNAL OF GRAPH THEORY, 1992, 16 (04) :355-374

[5] On graph irregularity strength [J].

Frieze, A ;

Gould, RJ ;

Karonski, M ;

Pfender, F .

JOURNAL OF GRAPH THEORY, 2002, 41 (02) :120-137

[6]

Hall P., 1935, J. London Math. Soc, V10, P26

[7]

Ivanco J., 2006, Discussiones Mathematicae Graph Theory, V26, P449, DOI 10.7151/dmgt.1337

[8]

Jacobson M.S., DEGREE IRREGULARITY

[9] Edge weights and vertex colours [J].

Karonski, M ;

Luczak, T ;

Thomason, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 91 (01) :151-157

[10] A tight bound on the irregularity strength of graphs [J].

Nierhoff, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (03) :313-323

← 1 2 →