Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Jakub Przybylo (3.12.2020)

vo štvrtok 3.12.2020 o 9:50 hod.

30. 11. 2020 10.13 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.


Stránka seminára