A method of enumeration of negative cycles of a signed graph (Q1916123): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Balancing signed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5626709 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the notion of balance of a signed graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On local balance and \(n\)-balance in signed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of balanced signed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On balance in group graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4742818 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5538757 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3988042 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumeration of weak isomorphism classes of signed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5682015 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: La reduction minimale d'un graphe à une reunion de cliques / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091990 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184913 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Characterizations of signed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Signed graphs / rank | |||
Normal rank |
Latest revision as of 12:00, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A method of enumeration of negative cycles of a signed graph |
scientific article |
Statements
A method of enumeration of negative cycles of a signed graph (English)
0 references
21 November 1996
0 references
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)].
0 references
enumeration
0 references
paths
0 references
cycles
0 references
signed graph
0 references
inclusion-exclusion principle
0 references
symmetric difference
0 references
divisibility
0 references