2025/08/12 by Gottwald, Kurt Klement, Hofmann, Tobias
#05C10 #05C40 #05C42 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.09336
This article investigates the connectivity dimension of a graph. We introduce this concept in analogy to the metric dimension of a graph, providing a graph parameter that measures the heterogeneity of the connectivity structure of a graph. We fully characterize extremal examples and present explicit constructions of infinitely many graphs realizing any prescribed non-extremal connectivity dimension. We also establish a general lower bound in terms of the graph's block structure, linking the parameter to classical notions from graph theory. Finally, we prove that the problem of computing the connectivity dimension is NP-complete.