Oddness

Home CAAGT Author Jan Goedgebeur

Oddness This page contains two independent programs for computing the oddness of a bridgeless cubic graph. The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph. Oddness_perf_matching computes the oddness by constructing perfect matchings and Oddness_2factor_slower computes the oddness by constructing 2-factors by searching for disjoint cycles. The program which constructs the perfect matchings is by far the fastest. The programs were used in the following manuscripts. G. Brinkmann, J. Goedgebeur, J. Hagglund and K. Markstrom, Generation and properties of Snarks, Journal of Combinatorial Theory, Series B, 103(4):468-488, 2013 (arXiv | DOI). J. Goedgebeur, On the smallest snarks with oddness 4 and connectivity 2, Electronic Journal of Combinatorics, 25(2), 5 pages, 2018 (arXiv). J. Goedgebeur, E. Máčajová and M. Škoviera, Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44, Ars Mathematica Contemporanea, 16(2): 277-298, 2019 (arXiv | DOI). The programs can be downloaded here. The programs are released under the GNU General Public License (GPL) and have been tested on Linux and Mac OS X. Installation instructions: Compile with: cc -O4 oddness_perf_matching.c -o oddness_perf_matching or cc -O4 oddness_2factor_slower.c -o oddness_2factor_slower Usage: ./<program> <number_of_vertices> < <inputfile> Remark: the inputgraphs are read from stdin in multicode format and the graphs with oddness at least 4 are written to stdout. Don't hesitate to contact me at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.