| Abstract: | A multigraph is (k,r)‐dense if every k‐set spans at most r edges. What is the maximum number of edges ex?(n,k,r) in a (k,r)‐dense multigraph on n vertices? We determine the maximum possible weight of such graphs for almost all k and r (e.g., for all r>k3) by determining a constant m=m(k,r) and showing that ex?(n,k,r)=m +O(n), thus giving a generalization of Turán's theorem. We find exact answers in many cases, even when negative integer weights are also allowed. In fact, our main result is to determine the maximum weight of (k,r)‐dense n‐vertex multigraphs with arbitrary integer weights with an O(n) error term. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 195–225, 2002 |
