2016/04/29 by Leslie Hogben, Hogben, Leslie, Jephian C. -H. Lin +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.1604.08817
arxiv created 2016/04/29 · openalex publication_date 2016/04/29 · arxiv updated 2016/05/02 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
A traditional Nordhaus-Gaddum problem for a graph parameter β is to find a (tight) upper or lower bound on the sum or product of β(G) and β(G) (where G denotes the complement of G). An r-decomposition G1,…,Gr of the complete graph Kn is a partition of the edges of Kn among r spanning subgraphs G1,…,Gr. A traditional Nordhaus-Gaddum problem can be viewed as the special case for r=2 of a more general r-part sum or product Nordhaus-Gaddum type problem. We determine the values of the r-part sum and product upper bounds asymptotically as n goes to infinity for the parameters tree-width and its variants largeur d'arborescence, path-width, and proper path-width. We also establish ranges for the lower bounds for these parameters, and ranges for the upper and lower bounds of the r-part Nordhaus-Gaddum type problems for the parameters Hadwiger number, the Colin de Verdière number μ that is used to characterize planarity, and its variants ν and ξ.