The extremal spectral radii of k -uniform supertrees

Honghai Li, Jia Yu Shao, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

51 Citations (Scopus)

Abstract

In this paper, we study some extremal problems of three kinds of spectral radii of k-uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence Q-spectral radius). We call a connected and acyclic k-uniform hypergraph a supertree. We introduce the operation of “moving edges” for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar Sn,k attains uniquely the maximum spectral radius among all k-uniform supertrees on n vertices. We also determine the unique k-uniform supertree on n vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path Pn,k attains uniquely the minimum spectral radius among all k-th power hypertrees of n vertices. Some bounds on the incidence Q-spectral radius are given. The relation between the incidence Q-spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.
Original languageEnglish
Pages (from-to)741-764
Number of pages24
JournalJournal of Combinatorial Optimization
Volume32
Issue number3
DOIs
Publication statusPublished - 1 Oct 2016

Keywords

  • Adjacency tensor
  • Hypergraph
  • Incidence Q-tensor
  • Signless Laplacian tensor
  • Spectral radius
  • Supertree

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this