Lexicographical ordering by spectral moments of bicyclic hypergraphs

Hong Zhou, Changjiang Bu · 2025

Read Lexicographical ordering by spectral moments of bicyclic hypergraphs by Hong Zhou, Changjiang Bu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-11907.txt.

Introduction

Hong Zhou and Changjiang Bu rank a family of hypergraphs by a fingerprint drawn from their spectra, in a 2025 paper. The fingerprint is the sequence of spectral moments, and the ranking it induces is called S-order. Their arena is linear bicyclic uniform hypergraphs: tidy structures carrying exactly two independent cycles. Two knobs vary, the girth and the number of edges.

For each girth and edge count, they identify which hypergraph comes first in the order and which comes last. Such bookends bracket the whole family and often expose the extremal shapes. The paper is a piece of pure combinatorics, settling the extremes of a ranking that chemists and network theorists use to sort molecular-like structures.

Catalog record

CREATORHong Zhou, Changjiang Bu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-11907

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lexicographical ordering by spectral moments of bicyclic hypergraphs Hong Zhou, Changjiang Bu Abstract For bicyclic hypergraphs, ordering by spectral moment ( S S -order) is investigated in this paper. We give the first and last hypergraphs in an S S -order of linear bicyclic uniform hypergraphs with given girth and number of edges. 1 Introduction For a k -uniform hypergraph \mathcal{H} with n vertices, the sum of d powers of all eigenvalues of the adjacency tensor \mathcal{A}_{\mathcal{H}} of \mathcal{H} is called the d th order spectral moment of \mathcal{H} , denoted by \mathrm{S}_{d}(\mathcal{H}) . The number of eigenvalues of \mathcal{A}_{\mathcal{H}} is n(k-1)^{n-1} [ 1 , 2 ] . For two k -uniform hypergraphs \mathcal{H}_{1} and \mathcal{H}_{2} with n vertices, if there exists an l\in\{1,2,\ldots,n(k-1)^{n-1}-1\} such that \mathrm{S}_{i}(\mathcal{H}_{1})=\mathrm{S}_{i}(\mathcal{H}_{2}) for i=0,1,\ldots,l-1 and \mathrm{S}_{l}(\mathcal{H}_{1})<\mathrm{S}_{l}(\mathcal{H}_{2}) , write \mathcal{H}_{1}\prec_{s}\mathcal{H}_{2} . If \mathrm{S}_{i}(\mathcal{H}_{1})=\mathrm{S}_{i}(\mathcal{H}_{2}) for i=0,1,\ldots,n(k-1)^{n-1}-1 , write \mathcal{H}_{1}=_{s}\mathcal{H}_{2} . The above order is called the S -order of hypergraphs [ 3 ] . Clearly, when \mathcal{H}_{1} and \mathcal{H}_{2} are 2-uniform, the above order is the S -order of graphs. The S -order of graphs had been used in producing graph catalogues [ 4 ] . In 1987, Cvetković and Rowlinson [ 5 ] gave some definitions concerning orderings of graphs including S -order. And the first and last graphs were given in an S -order of trees with given number of vertices, unicyclic graphs with given girth and number of vertices, respectively. Wu and Fan [ 6 ] characterized the first and last graphs in an S -order of bicyclic graphs with given number of vertices. Some results on an S -order have been obtained in the literature: see WU20101707 , PAN20111265 , CHENG2012858 for trees, CHENG20121123 for unicyclic graphs and SHUCHAO2013ON , 10.1216/RMJ-2016-46-1-261 for connected graphs. The study of spectral hypergraph theories via tensors has attracted extensive attention clark2021harary , cooper2 , doi:10.1137/21M1404740 , 2022Thestabilizing , especially the spectral moment of hypergraphs clark2021harary , ref23 . Shao et al. established some formulas for the trace of tensors in terms of some graph parameters shao2015some . When the tensor is an adjacency tensor, the above formulas are the formulas for spectral moments of hypergraphs. Fan et al. gave a formula for the spectral moment of hypergraphs in terms of the number of arborescences FAN202389 . Clark and Cooper gave an expression for the spectral moment of hypergraphs and used this result to give the “Harary-Sachs” coefficient theorem for hypergraphs clark2021harary . A formula for the spectral moment of hypertrees and power hypergraphs was given, respectively doi:10.1080/03081087.2021.1953431 , ref23 . In this paper, for k\geq 3 , the explicit expressions of 2k th and 3k th order spectral moments of linear bicyclic k -uniform hypergraphs are obtained in terms of the number of some subhypergraphs. And we get when k\nmid d , the d th order spectral moment of linear bicyclic k -uniform hypergraphs is equal to 0 . Using expressions of spectral moments and operations of moving edges, we give the first and last hypergraphs in an S -order of linear bicyclic uniform hypergraphs with given girth and number of edges. 2 Preliminaries A hypergraph \mathcal{H} is called k -uniform if every edge of \mathcal{H} contains exactly k vertices. A vertex of \mathcal{H} is called a cored vertex if it has degree one. An edge e of \mathcal{H} is called a pendant edge if it contains exactly |e|-1 cored vertices. A cored vertex in a pendant edge is also called a pendant vertex . A hypergraph \mathcal{H} is called linear if any two edges intersect into at most one vertex. The k -power hypergraph G^{(k)} is the hypergraph which is obtained by adding k-2 vertices with degree one to each edge of the graph G . Let P_{q} , S_{q} and C_{q} denote the path, the star and the cycle with q edges, respectively. A k -uniform hypergraph \mathcal{H} is called k -partite, if the vertices of \mathcal{H} can be partitioned into k sets so that every edge uses exactly one vertex from each set cooper2012spectra . A k -uniform hypergraph \mathcal{H}=(V,E) is called hm -bipartite if there is a disjoint partition of the vertex set V as V=V_{1}\bigcup V_{2} such that V_{1},V_{2}\neq\emptyset and every edge in E intersects V_{1} in exactly one vertex and V_{2} the other k-1 vertices 2014cccA . Let \mathcal{H}=(V,E) be a k -uniform hypergraph. If for every edge e\in E , there is a vertex i_{e}\in e such that the degree of the vertex i_{e} is one, then \mathcal{H} is a cored hypergraph 2013Cored . The spectrum of a k -uniform hypergraph is said to be k -symmetric if this spectrum is invariant under a rotation of an angle 2\pi/k in the complex plane shao2015some . A connected k -uniform hypergraph \mathcal{H} with n vertices and m edges is called bicyclic if n=m(k-1)-1 . For k\geq 3 , all linear bicyclic k -uniform hypergraphs with n vertices and m edges consist of the following two types \mathcal{B}_{n}^{k} and \mathcal{C}_{n}^{k} . For three integers p,q,l with q\geq p\geq 3 and l\geq 0 , let C_{1}(resp.,C_{2}) be a k -uniform hypercycle of length p (resp., q ) and P=(u_{0},e_{1},u_{1},\ldots,e_{l},u_{l}) be a k -uniform hyperpath of length l . Let v_{1,1}\in V(C_{1}),v_{2,1}\in V(C_{2}) be two arbitrary vertices with degree 1, and let v_{1,2}\in V(C_{1}),v_{2,2}\in V(C_{2}) be two arbitrary vertices with degree 2. For n^{\prime}=(p+q+l)(k-1)-1 , let B_{1,n^{\prime},p,l,q}^{k} be the n^{\prime} -vertex k -uniform bicyclic hypergraph obtained by identifying v_{1,2} with u_{0} , and identifying v_{2,2} with u_{l} , let B_{2,n^{\prime},p,l,q}^{k} be the n^{\prime} -vertex k -uniform bicyclic hypergraph obtained by identifying v_{1,2} with u_{0} , and identifying v_{2,1} with u_{l} , and let B_{3,n^{\prime},p,l,q}^{k} be the n^{\prime} -vertex k -uniform bicyclic hypergraph obtained by identifying v_{1,1} with u_{0} , and identifying v_{2,1} with u_{l} . For n\geq n^{\prime} and i\in\{1,2,3\} , let \mathcal{B}_{i,n,p,l,q}^{k} be the set of n -vertex m -edge k -uniform bicyclic hypergraphs each of which contains B_{i,n^{\prime},p,l,q}^{k} as a sub-hypergraph, where m=\frac{n+1}{k-1} . And B_{i,n^{\prime},p,l,q}^{k} is called the base of \mathcal{B}_{i,n,p,l,q}^{k} . Let \mathcal{B}_{n}^{k}=\bigcup_{i=1}^{3}\{\mathcal{B}_{i,n,p,l,q}^{k}~|~q\geq p\geq 3,l\geq 0\} . Moreover, let B_{1,n,p,0,q}^{k}(m-p-q) denote the k -uniform bicyclic hypergraph obtained from B_{1,n^{\prime},p,0,q}^{k} by attaching m-p-q pendant edges at the unique vertex with degree 4, where m=\frac{n+1}{k-1} . Let P_{p}=(u_{1},e_{1},u_{2},\ldots,e_{p},u_{p+1}),P_{q}=(v_{1},f_{1},v_{2},\ldots,f_{q},v_{q+1}) and P_{l}=(w_{1},g_{1},\\ w_{2},\ldots,g_{l},w_{l+1}) be three k -uniform hyperpaths, and suppose (p+q+l)(k-1)-1=n^{\prime} . For three integers p,q,l with p=1,1<q\leq l and 1<p\leq q\leq l , let C_{1,n^{\prime},p,q,l}^{k} be the n^{\prime} -vertex k -uniform bicyclic hypergraph obtained from P_{p},P_{q} and P_{l} by identifying three vertices u_{1},v_{1},w_{1}, and identifying three vertices u_{p+1},v_{q+1},w_{l+1} . For q>1,1\leq p\leq q-1\leq l and q=1,1<p\leq l , let C_{2,n^{\prime},p,q,l}^{k} be the n^{\prime} -vertex k -uniform bicyclic hypergraph obtained from P_{p},P_{q} and P_{l} by identifying three vertices u_{1},v_{1},w_{1} , identifying u_{p+1} with v_{q+1} , and identifying w_{l+1} with v , respectively, where v\in f_{q}\setminus\{v_{q},v_{q+1}\} . For q>2,1\leq p\leq q-2\leq l and q=2,1\leq p\leq l and q=1,k>3,1<p\leq l , let C_{3,n^{\prime},p,q,l}^{k} be the n^{\prime} -vertex k -uniform bicyclic hypergraph obtained from P_{p},P_{q} and P_{l} by identifying u_{1} with v_{1} , identifying u_{p+1} with v_{q+1} , identifying w_{1} with v^{\prime} , and identifying w_{l+1} with v^{\prime\prime} , respectively, where v^{\prime}\in f_{1}\setminus\{v_{1},v_{2}\} and v^{\prime\prime}\in f_{q}\setminus\{v_{q},v_{q+1}\} . (in the special case q=1 , we choose v^{\prime}\neq v^{\prime\prime}

Read the complete text