Seminár z teórie grafov - Jakub Przybylo (3.12.2020)
vo štvrtok 3.12.2020 o 9:50 hod.
Od: Martin Škoviera
Prednášajúci: Jakub Przybylo (AGH University of Science and Technology, Krakow)
Názov: The irregularity strength of regular graphs is usually small
Termín: 3.12.2020, 9:50 hod.
Prístupový kód do MS TEAMS (pre používateľov z UK): gglxxc7
Pripojenie (pre hostí mimo UK)
The irregularity strength of a graph G, s(G), is the least k admitting a [k]-weighting of the edges of G assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of G via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant C such that s(G) is at most n/d+C for each d-regular graph G with n vertices and d at least 2. However, the best published result thus far implies an upper bound 6n/d+C. We shall show that the conjecture of Faudree and Lehel holds asymptotically in the cases when d is neither very small nor very close to n.