×

Irregular assignments and two problems à la Ringel. (English) Zbl 0752.05034

Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel, 29-36 (1990).
[For the entire collection see Zbl 0698.00017.]
A weighting \(w\) of a simple graph \(G\) is a function that assigns to each edge of \(G\) a positive integer. The weighting \(w\) is said to be admissible if the sums of the weights at each vertex are all distinct. This paper is concerned with the evaluation of the parameter \(i(G)\), which is the minimum cardinality of the image of \(w\) over all admissible weightings \(w\) of \(G\). The authors evaluate \(i(G)\) for complete graphs, complete bipartite graphs, cycles, paths, irreducible trees, and several other families of graphs. They also prove that if \(G\) is a graph of order \(n\) such that \(i(G)\) is finite, then \(i(G)\leq n-1\), except that \(i(K_ 3)=3\).
Reviewer: S.Stahl (Lawrence)

MSC:

05C35 Extremal problems in graph theory
05C99 Graph theory

Citations:

Zbl 0698.00017