Irregular networks, regular graphs and integer matrices with distinct row and column sums
A network is a simple graph to which each edge is assigned a positive integer value or weight. The degree of a vertex in a network is the sum of weights of its incident edges. A network is irregular if all the vertices have distinct degrees. The strength of a network is the maximum weight assigned to any edge, while the irregularity strength s(G) of a graph G is the minimum strength among irregular networks with underlying graph G. It is known that if G is an r-regular graph of order n then \(s(G)\geq (n+r-1)/r.\) In this paper infinitely many r-regular graphs with \(s(G)=(n+r-1)/r\) are exhibited and it is proved that \(s(G)\leq [n/2]+2\) if r is even. Also positive integer matrice with distinct row and column sums having the smallest possible maximal entry are studied.
scientific article; zbMATH DE number 4122026