A method of enumeration of negative cycles of a signed graph (Q1916123): Difference between revisions

A method for the enumeration of negative paths or cycles of a signed graph is developed, based upon the inclusion-exclusion principle for the symmetric difference. Some interesting divisibility properties by high powers of 2 of the number of such configurations are deduced; e.g., for every complete signed graph of order \(n\), the number of negative \(k\)-cycles (resp. \(k\)-paths) \((3\leq k\leq n)\) is divisible by \(2^{k- 2- \lfloor\log_2(k- 1)\rfloor}\) (resp. by \(2^{k- 1- \lfloor\log_2 k\rfloor})\). These evaluations are strong and extend some divisibility properties deduced by the reviewer [Math. Sci. Hum. 53, 63-67 (1976; Zbl 0327.05119)].