×

Irregular networks. (English) Zbl 0671.05060

Graph theory, 250th Anniv. Conf., Lafayette/Indiana 1986, Congr. Numerantium 64, 197-210 (1988).
Summary: [For the entire collection see Zbl 0663.00003.]
A network N is a graph in which each edge is assigned a positive integer weight. The degree of a vertex in N is the sum of the weights of its incident edges. A network is irregular if its vertices have distinct degrees. The strength of a network N is the maximum weight among the edges of N. The irregularity strength s(G) of a graph G is the minimum strength among the irregular networks having G as an underlying graph. It is shown that s(G) is defined for every connected graph G of order \(p\geq 3\) and that s(G)\(\leq 2p-3\). Further, if N is a network of strength at least 2, then there exists an irregular network having same strength as N and containing N as an induced subnetwork.

MSC:

05C99 Graph theory
05C75 Structural characterization of families of graphs

Citations:

Zbl 0663.00003