Nordhaus-Gaddum-type theorems for maximum average degree

Abstract

A $k$-decomposition $(G_1,\dots ,G_k)$ of a graph $G$ is a partition of its edge set into $k$ spanning subgraphs $G_1,\dots ,G_k$. The classical theorem of Nordhaus and Gaddum bounds $\ddot{I}‡(G_1)+\ddot{I}‡(G_2)$ and $\ddot{I}‡(G_1)\ddot{I}‡(G_2)$ over all 2-decompositions of $K_n$. For a graph parameter $p$, let $p(k,G)=\max \{{\sum }_{i=1}^{k}p(Gi)\}$, taken over all $k$-decompositions of graph $G$. In this paper we consider $M(k,K_n)=M(k,n)=\max \{{\sum }_{i=1}^k\mathrm{Mad}(G_i)\}$, taken over all $k$-decompositions of the complete graph $K_n$, where $\mathrm{Mad}(G)$ denotes the maximum average degree of $G$, $\mathrm{Mad}(G)=\max \{2e(H)/|H|:H\subseteq G\}=\max \{d(H):H\subseteq G\}$. Among the many results obtained in this paper we mention the following selected ones. (1) $M(k,n)<\sqrt{k}n$, and ${\lim }_{k\to \infty }({\mathrm{liminf}}_{n\to \infty }\frac{M(k,n)}{\sqrt{k}n})=1$. (2) Exact determination of $M(2,n)$. (3) Exact determination of $M(k,n)$ when $k=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-t$, $0\le t\le (n-1{)}^2/3$. Applications of these bounds to other parameters considered before in the literature are given.

improved wording, inserted proposition 52, revised concluding section, enhanced references; 48 pages