Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Jakub Przybylo (3.12.2020)

Thursday 3.12.2020 at 9:50

30. 11. 2020 10.16 hod.
By: Martin Škoviera

Jakub Przybylo (AGH University of Science and Technology, Krakow):
The irregularity strength of regular graphs is usually small

MS TEAMS code (users from Comenius University in Bratislava): gglxxc7 
Link (guests outside Comenius University in Bratislava)

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.

More information