Irregular networks, regular graphs and integer matrices with distinct row and column sums
type: Item
instance of: scholarly article
title: Irregular networks, regular graphs and integer matrices with distinct row and column sums
zbMATH Open document ID: 0685.05029
DOI: 10.1016/0012-365X(89)90321-X
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 94C99
zbMATH DE Number: 4122026
zbMATH Keywords: biparticle graph
zbMATH Keywords: strength of a network
zbMATH Keywords: regular graph
author: Ralph Faudree
author: R. H. Schelp
author: Michael Jacobson
author: Jeno Lehel
reviewed by: Vladimir Fleischer
MaRDI profile type: Publication
cites work: Q3824455
cites work: Some Theorems on Abstract Graphs
cites work: Sum-distinct sequences and Fibonacci numbers
description: scientific article; zbMATH DE number 4122026