22/11/2022 de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"
Ponente: Linda Lesniak
Institución: Western Michigan University
A graph is called Hamiltonian if it contains a spanning cycle. 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 similar sufficient condition of Bondy for forcible k-connectedness is not necessary in the same way, where a graph G is called k-connected if at least k vertices must be removed from G to result in a disconnected graph.
Temas: