Cycles dans les produits cartésiens de graphes
Time: 14:30 -- Location: LRI, 455
Résumé : Les cycles dans les graphes ont été largement étudiés : cycles hamiltoniens, cycles de toutes les longueurs, cycles contenant des sommets ou des arêtes donnés, .... Nous passons en revue quelques-uns des résultats essentiels du domaines avant de nous intéresser à l'existence de cycles dans les produits cartésiens de graphes. L'intérêt pour ce problème remonte entre autres à la conjecture de Barnette (1966) qui a conduit à l'étude des cycles hamiltoniens dans les prismes de graphes et les produits cartésiens par des cliques ou des cycles. Depuis, on a étudié de nombreuses propriétés cycliques des produits cartésiens, nous en rappelons quelque-unes et donnons des résultats plus récents sur les cycles dans les prismes généralisés.
Summary: Cycles in graphs have been extensively studied : hamiltonian cycles, cycles of every length, cycles containing given vertices or given edges, .... We review some of the main results in the domain and focus on the existence of cycles in cartesian products of graphs. The interest for this problem goes back, among other things, to Barnette's Conjecture (1966). It led to partial results on hamiltonian cycles in prisms of graphs and in cartesian product by a clique or a cycle. Since then, many cyclic properties of cartesian products of graphs have been discovered, we will survey some of them and give more recent results on cycles in generalized prisms.