# 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
##### Keywords:
network; irregularity strength; irregularity cost
Full Text:
##### References:
  Aigner, M.; Triesch, E., Irregular assignments of trees and forests, preprint nr. A 89-9, (1989), Freie Universität Berlin, to appear  Chartrand, G.; Jacobson, M.S.; Lehel, J.; Oellerman, O.R.; Ruiz, S.; Saba, F., Irregular networks, (), 187-192  Faudree, R.J.; Jacobson, M.S.; Kinch, L.; Lehel, J., Irregularity strength of dense graphs, Discrete math., 91, 45-59, (1991) · Zbl 0755.05092  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  Faudree, R.J.; Lehel, J.; Faudree, R.J.; Lehel, J., Bound on the irregularity strength of regular graphs, (), 247-256 · Zbl 0697.05048  Jacobson, M.S.; Kubicka, E.; Kubicki, G., Irregularity sum for graphs, (1992), to appear  Jendroľ, S.; Tkáč, M., The irregularity strength of tkp, Discrete math., 145, 301-305, (1995) · Zbl 0834.05029  Kinch, L.; Lehel, J., The irregularity strength of tp3, Discrete math., 94, 75-79, (1991) · Zbl 0778.05079  Lehel, J., Facts and quests on degree irregular assignments, (), 765-782 · Zbl 0841.05052  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.