Chartrand, Gary; Jacobson, Michael S.; Lehel, Jenö; Oellermann, Ortrud R.; Ruiz, Sergio; Saba, Farrokh 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. Cited in 5 ReviewsCited in 63 Documents MSC: 05C99 Graph theory 05C75 Structural characterization of families of graphs Keywords:network; degree; irregularity strength; irregular networks Citations:Zbl 0663.00003 PDFBibTeX XML