Irregular networks, regular graphs and integer matrices with distinct row and column sums.

*(English)*Zbl 0685.05029A 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.

Reviewer: V.Fleischer

PDF
BibTeX
XML
Cite

\textit{R. J. Faudree} et al., Discrete Math. 76, No. 3, 223--240 (1989; Zbl 0685.05029)

Full Text:
DOI

##### References:

[1] | G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular Networks, to appear. · Zbl 0671.05060 |

[2] | Dirac, G., Some theorems on abstract graphs, Proc. London math. soc., 2, 69-81, (1952) · Zbl 0047.17001 |

[3] | M.S. Jacobson, L. Kinch and J. Lehel, Sequences generating distinct sums, in preparation. · Zbl 0702.11009 |

[4] | M.S. Jacobson and J. Lehel, A bound for the strength of an irregular network, submitted. |

[5] | Petersen, J., Die theorie der regulĂ¤ren graphen, Acta math., 15, 193-220, (1891) · JFM 23.0115.03 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.