Home > Timetable > Contribution details


Odd Cycle Bases of Nonbipartite Graphs


  • Prof. Donovan HARE

Primary authors


The cycle space of a graph $G$ is the subspace of the edge space of $G$ over the 2-element field that is spanned by the cycles of $G$ (considered as edge-sets of $G$). Bondy and Lov\'{a}sz (1981) showed that the cycles through any set of $s-1$ vertices in an $s$-connected graph generate its cycle space. But what if these cycles are restricted to be of odd length?

In this talk, we consider this question and others regarding the cycle bases of nonbipartite graphs all of whose cycles are of odd length. It will be proved that if the graph is 3-connected and nonbipartite, then its cycle space can be generated by all odd cycles through a fix vertex. An example of Toft (1975) is used to show that two fixed vertices cannot be specified, contrasting the result of Bondy and Lov\'{a}sz when parity isn't a consideration. Other related results regarding the number of odd cycles in nonbipartite graphs will also be discussed.