Odd Cycle Bases of Nonbipartite Graphs

Not scheduled
UP FHS (Koper)



Titov trg 5,Koper


Prof. Donovan Hare (University of British Columbia)


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.

Primary author

Prof. Donovan Hare (University of British Columbia)

Presentation Materials

There are no materials yet.