Graph pairs and their entropies: Modularity problems (Q5928569)

From MaRDI portal
scientific article; zbMATH DE number 1583104
Language Label Description Also known as
English
Graph pairs and their entropies: Modularity problems
scientific article; zbMATH DE number 1583104

    Statements

    Graph pairs and their entropies: Modularity problems (English)
    0 references
    0 references
    0 references
    1 April 2001
    0 references
    If the union of graphs \(F\), \(G\) on the same vertex set is the complete graph then for every probability distribution \(P\), the inequality \(H(F\cup G,P)+H(F\cap G,P)\leq H(F,P)+H(G,P)\) holds if and only if there is no 3-vertex set containing one edge of each of \(F-G\), \(G-F\), and \(F\cap G\), where \(H(G,P)\) is the graph entropy. \(F\) and \(G\) form a supermodular pair if and only if on no subset of the vertex set are \(F\), \(G\) edge-disjoint and imperfect. For this two proofs are given, one based on the description of the graph entropy in terms of the fractional chromatic number.
    0 references
    entropy of graphs
    0 references
    submodularity
    0 references
    probability distribution
    0 references
    fractional chromatic number
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references