Group irregularity strength of connected graphs

被引：10

作者：

Anholcer, Marcin ^{[1
,2
]}

Cichacz, Sylwia ^{[2
,3
]}

Milanic, Martin ^{[2
,4
]}

机构：

[1] Poznan Univ Econ, Fac Informat & Elect Econ, PL-61875 Poznan, Poland

[2] Univ Primorska, UP FAMNIT, SI-6000 Koper, Slovenia

[3] AGH Univ Sci & Technol, Fac Appl Math, PL-30059 Krakow, Poland

[4] Univ Primorska, UP IAM, SI-6000 Koper, Slovenia

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2015年 / 30卷 / 01期

关键词：

Irregularity strength; Graph labelling; Abelian group; TREES;

D O I：

10.1007/s10878-013-9628-6

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We investigate the group irregularity strength () of graphs, that is, we find the minimum value of such that for any Abelian group of order , there exists a function such that the sums of edge labels at every vertex are distinct. We prove that for any connected graph of order at least , if and otherwise, except the case of an infinite family of stars. We also prove that the presented labelling algorithm is linear with respect to the order of the graph.

引用

页码：1 / 17

页数：17

共 19 条

[1] IRREGULAR ASSIGNMENTS OF TREES AND FORESTS [J].

AIGNER, M ;

TRIESCH, E .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (04) :439-449

[2] Irregularity strength of trees [J].

Amar, D ;

Togni, O .

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

[3]

Anholcer M, 2013, PREPRINT

[4] HARMONIOUS GROUPS [J].

BEALS, R ;

GALLIAN, JA ;

HEADLEY, P ;

JUNGREIS, D .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1991, 56 (02) :223-238

[5]

Cavenagh N, 2006, ELECT J COMBIN R, VR92, P19

[6]

Chartrand G., 1988, Congr. Numer., V64, P197

[7]

Combe D., 2004, Australasian Journal of Combinatorics, V29, P259

[8] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[9] An iterative approach to graph irregularity strength [J].

Ferrara, Michael ;

Gould, Ronald ;

Karonski, Michal ;

Pfender, Florian .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (11) :1189-1194

[10]

Froncek D, 2013, AUSTRALAS J COMB, V55, P167

← 1 2 →