Nordhaus–Gaddum‐Type Theorems for Maximum Average Degree

Abstract

ABSTRACT A ‐decomposition of a graph is a partition of its edge set into spanning subgraphs . The classical theorem of Nordhaus and Gaddum bounds and over all 2‐decompositions of . For a graph parameter , let , taken over all ‐decompositions of graph . In this paper, we consider , taken over all ‐decompositions of the complete graph , where denotes the maximum average degree of . Among the many results obtained, we mention the following selected ones. , and . Exact determination of . Exact determination of when . A main tool used along this paper is the following list variant of Nordhaus–Gaddum, which is of independent interest and can be adopted to attack other Nordhaus–Gaddum type problems, too. A list of graphs is a multiset, , where repetitions are allowed. For a positive integer define taken over all lists of graphs such that . Clearly . We determine for all values of the parameters involved: Let be any integers, and let be non‐negative integers such that , where and . Then if , and if . An extended version of this paper, including further constructions and applications to other parameters considered before in the literature, can be found in arXiv:2505.04929.