Bonferroni inequalities and negative cycles in large complete signed graphs
type: Item
instance of: scholarly article
title: Bonferroni inequalities and negative cycles in large complete signed graphs
zbMATH Open document ID: 0861.05036
author: Dragos-Radu Popescu
author: Ioan Tomescu
published in: European Journal of Combinatorics
publication date: 1997-05-04T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 930072
zbMATH Keywords: signed graph
zbMATH Keywords: extremal graphs
zbMATH Keywords: Bonferroni inequalities
zbMATH Keywords: probability
MaRDI profile type: Publication
OpenAlex ID: W2037243969
DOI: 10.1006/EUJC.1996.0041
description: scientific article; zbMATH DE number 930072