zbMATH — the first resource for mathematics

The irregularity strength and cost of the union of cliques. (English) Zbl 0852.05054
A network $$G(w)$$ consists of a graph $$G$$ together with a mapping $$w$$ of its edge set into the set of positive integers; the value $$w(e)$$ is called the weight of the edge $$e$$. The strength $$s(G(w))$$ of the network $$G(w)$$ is the maximum of $$w(e)$$ over all edges $$e$$ of $$G$$. The weighted degree of a vertex $$x$$ of $$G$$ is the sum of weights of edges which are incident to $$x$$. If no two vertices have the same weighted degree, the network $$G(w)$$ is called irregular. The irregularity strength $$s(G)$$ of $$G$$ is the minimum of $$s(G(w))$$ over all irregular networks $$G(w)$$ with the underlying graph $$G$$. A similar concept is the irregularity cost. The main result of the paper is the theorem determining the irregularity strength of the disjoint union $$\bigcup^n_{i= 1} t_i K_{p_i}$$ of cliques. Some results concerning the irregularity cost are added.

MSC:
 05C35 Extremal problems in graph theory
Full Text:
References:
 [1] Aigner, M.; Triesch, E., Irregular assignments of trees and forests, preprint nr. A 89-9, (1989), Freie Universität Berlin, to appear [2] Chartrand, G.; Jacobson, M.S.; Lehel, J.; Oellerman, O.R.; Ruiz, S.; Saba, F., Irregular networks, (), 187-192 [3] Faudree, R.J.; Jacobson, M.S.; Kinch, L.; Lehel, J., Irregularity strength of dense graphs, Discrete math., 91, 45-59, (1991) · Zbl 0755.05092 [4] Faudree, R.J.; Jacobson, M.S.; Lehel, J.; Schelp, R.H., Irregular networks, regular graphs and integer matrices with distinct row and columm sums, Discrete math., 76, 223-240, (1989) · Zbl 0685.05029 [5] Faudree, R.J.; Lehel, J.; Faudree, R.J.; Lehel, J., Bound on the irregularity strength of regular graphs, (), 247-256 · Zbl 0697.05048 [6] Jacobson, M.S.; Kubicka, E.; Kubicki, G., Irregularity sum for graphs, (1992), to appear [7] Jendroľ, S.; Tkáč, M., The irregularity strength of tkp, Discrete math., 145, 301-305, (1995) · Zbl 0834.05029 [8] Kinch, L.; Lehel, J., The irregularity strength of tp3, Discrete math., 94, 75-79, (1991) · Zbl 0778.05079 [9] Lehel, J., Facts and quests on degree irregular assignments, (), 765-782 · Zbl 0841.05052 [10] Tuza, Zs., How to make a random graph irregular, (), to appear · Zbl 0821.05050
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.