Bonferroni inequalities and negative cycles in large complete signed graphs (Q1922875): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2037243969 / rank | |||
Normal rank |
Latest revision as of 20:58, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bonferroni inequalities and negative cycles in large complete signed graphs |
scientific article |
Statements
Bonferroni inequalities and negative cycles in large complete signed graphs (English)
0 references
4 May 1997
0 references
A signed graph \(G\) based on \(F\) is an ordinary graph \(F\) with each edge marked as positive or negative. The authors only consider the case in which \(F\) is the complete graph \(K_n\). A cycle of \(K_n\) is said to be negative if it contains an odd number of negative edges; otherwise, it is positive. The authors solve the problem of characterizing extremal graphs \(K_n\) relative to the number of negative \(p\)-cycles, when the number of negative edges is fixed, and when \(n\) is large. They also show that the number of negative \(p\)-cycles can be expressed as an alternating sum for which the Bonferroni inequalities hold. Furthermore, the asymptotic value of the probability that a \(p\)-cycle of \(K_n\) is negative is found as \(n\to\infty\), if the negative edges induce a subgraph whose components are paths or cycles.
0 references
signed graph
0 references
extremal graphs
0 references
Bonferroni inequalities
0 references
probability
0 references