Name
Abstract | ||
|---|---|---|
We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/BF01204721 | Combinatorica |
Keywords | Field | DocType |
complete graph,perfect graph,call graph | Perfect graph,Discrete mathematics,Comparability graph,Combinatorics,Line graph,Distance-hereditary graph,Cograph,Trivially perfect graph,Perfect graph theorem,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
12 | 2 | 1439-6912 |
Citations | PageRank | References |
12 | 1.49 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Körner | 1 | 12 | 1.49 |
| Gábor Simonyi | 2 | 249 | 29.78 |
| Zsolt Tuza | 3 | 1889 | 262.52 |