On the necessity of Chvátal’s hamiltonian degree condition and other forcibly P degree conditions
Ponente: Linda Lesniak
Institución: Western Michigan University
Tipo de Evento: Investigación
Institución: Western Michigan University
Tipo de Evento: Investigación
| Cuándo |
26/11/2022 de 13:00 a 14:00 |
|---|---|
| Dónde | ZOOM ID 882 9372 3602 |
| Agregar evento al calendario |
vCal
iCal
|
In 1972 Chvátal gave a well-known sufficient condition for a graphical sequence to be forcibly hamiltonian, and showed that in some sense his condition is best possible. Even though, for each n ≥ 3, we have constructed exponentially many forcibly hamiltonian n-sequences that do not satisfy Chvátal’s condition, in this talk we will discuss why we conjecture that the proportion of forcibly hamiltonian n-sequences that satisfy Chvátal’s condition approaches 1 exponentially fast. Informally, with probability approaching 1 as n → ∞, we conjecture that a graphical n-sequence π is forcibly hamiltonian if and only
if π satisfies Chvátal’s condition. In contrast, we can essentially prove that for every k ≥ 1 the sufficient condition of Bondy and Boesch for forcible k-connectedness is not necessary in the same way. This suggests a more general question for other monotone graphical properties P that we will discuss here.
