The k-core of a graph and its high-order spectra

2025/12/05 by Liu, Chunmeng, Xu, Qing, Bu, Changjiang
#05C50 #05C69 #15A69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2512.05351

Abstract

The k-core of a graph is its largest subgraph with minimum degree at least k, a fundamental concept for uncovering hierarchical structures. In this paper, we establish a connection between the k-core and the high-order spectra of graphs, a concept originally introduced by Cvetković, Doob, and Sachs. Specifically, we consider the high-order spectra defined via the k-adjacency tensor. Within this framework, we prove that a graph admits a non-empty k-core if and only if the spectral radius of the k-adjacency tensor is greater than or equal to 1. Moreover, when the k-core exists, vertices corresponding to positive entries in the Perron vector of the k-adjacency tensor belong to the k-core. We thus define the k-order eigenvector centrality via the Perron vector, which provides both membership identification and a measure of relative influence within the k-core. Numerical experiments confirm our theoretical findings and illustrate the properties of this centrality measure in some real-world networks.

Citations

• The high order spectral radius of graphs without long cycles or paths
• Perron-Frobenius theorem for dual tensors and its applications
• Critical Nodes Identification in Complex Networks: A Survey
• A tensor's spectral bound on the clique number
• The subgraph eigenvector centrality of graphs
• The high order spectral extremal results for graphs and their applications
• On a generalization of the spectral Mantel's theorem
• Node and Edge Nonlinear Eigenvector Centrality for Hypergraphs
• Characterizing cycle structure in complex networks
• A Harary-Sachs Theorem for Hypergraphs
• Three hypergraph eigenvector centralities
• The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs
• Moore–Penrose inverse of tensors via Einstein product
• The Spacey Random Walk: A Stochastic Process for Higher-Order Data
• On the first and second eigenvalue of finite and infinite uniform hypergraphs
• PageRank beyond the Web
• PageRank Beyond the Web
• Spectra of Uniform Hypergraphs
• Spectra of uniform hypergraphs
• Most tensor problems are NP-hard
• Most Tensor Problems Are NP-Hard
• Perron–Frobenius theorem for nonnegative multilinear forms and extensions
• Some unique properties of eigenvector centrality
• Power and Centrality: A Family of Measures
• Network structure and minimum degree

Related

• Cores, shell indices and the degeneracy of a graph limit
• An α-triangle eigenvector centrality of graphs
• High-ordered spectral characterization of unicyclic graphs
• The core index of a graph
• Three hypergraph eigenvector centralities