2025/05/08 by Yair Caro, Caro, Yair, Źsolt Tuza +1
Computer Science · Engineering · Mathematics · #05B05 #05C07 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2505.04929
openalex publication_date 2025/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A k-decomposition (G1,…,Gk) of a graph G is a partition of its edge set into k spanning subgraphs G1,…,Gk. The classical theorem of Nordhaus and Gaddum bounds χ(G1) + χ(G2) and χ(G1) χ(G2) over all 2-decompositions of Kn. For a graph parameter p, let p(k,G) = max \ ∑i=1k p(Gi) \, taken over all k-decompositions of graph G. In this paper we consider M(k,Kn) = M(k,n) = max \ ∑i=1k Mad(Gi) \, taken over all k-decompositions of the complete graph Kn, where Mad(G) denotes the maximum average degree of G, Mad(G) = max \ 2e(H)/|H| : H ⊆ G \ = max \d(H) : H ⊆ G \. Among the many results obtained in this paper we mention the following selected ones. (1) M(k, n) < √(k) n, and limk→∞ ( \liminfn→∞ (M(k,n))/(√(k) n) ) = 1. (2) Exact determination of M(2,n). (3) Exact determination of M(k,n) when k = \binomn2 - t, 0 ≤ t≤ (n-1)2/3. Applications of these bounds to other parameters considered before in the literature are given.