THE TRACE OF UNIFORM HYPERGRAPHS WITH APPLICATION TO ESTRADA INDEX YI-ZHENG FAN JIAN ZHENG AND YA YANG

2025-05-06 0 0 572.09KB 27 页 10玖币

侵权投诉

THE TRACE OF UNIFORM HYPERGRAPHS WITH APPLICATION TO

ESTRADA INDEX

YI-ZHENG FAN*, JIAN ZHENG, AND YA YANG

Abstract. In this paper we investigate the traces of the adjacency tensor of hypergraphs (simply

called the traces of hypergraphs). We give new expressions for the traces of hypertrees and linear

unicyclic hypergraphs by the weight function assigned to their connected sub-hypergraphs, and

provide some perturbation results for the traces of a hypergraph with cut vertices. As applications

we determine the unique hypertree with maximum Estrada index among all hypertrees with ﬁxed

number of edges and perfect matchings, and the unique unicyclic hypergraph with maximum

Estrada index among all unicyclic hypergraph with ﬁxed number of edges and girth 3.

1. Introduction

Ahypergraph H= (V, E) consists of a vertex set V={v1, v2,· · ·, vn}denoted by V(H) and an

edge set E={e1, e2,· · ·, ek}denoted by E(H), where ei⊆Vfor i∈[k]. If there exist no diﬀerent

iand jsuch that ei⊆ej, then His called simple. If |ei|=mfor each i∈[k] and m≥2, then H

is called an m-uniform hypergraph. A simple graph is exactly a simple 2-uniform hypergraph.

For an m-uniform hypergraph Hon vertices v1, . . . , vn. Cooper and Dutle [7] introduced the

adjacency tensor of Has follows.

Deﬁnition 1.1. ( [7]) Let Hbe an m-uniform hypergraph on nvertices v1, v2, . . . , vn. The

adjacency tensor of His deﬁned as A(H)=(ai1i2...im), an m-th order n-dimensional tensor, where

ai1i2...im=(1

(m−1)! ,if {vi1, . . . , vim} ∈ E(H);

0,else.

Note that if m= 2, then A(H) is exactly the usual adjacency matrix of the simple graph H. In

this situation, the d-th trace of A(H), namely the trace of A(H)d, is exactly the number of closed

walks of Hwith length dstarting from each vertex of H.

To deal with the high order case, Morozov and Shakirov [33] introduced the traces of polynomial

maps fgiven by a system of homogeneous polynomials of arbitrary degrees. As a tensor T=

(ti1i2...im) of order mand dimension nnaturally induces a system of homogeneous polynomials

2000 Mathematics Subject Classiﬁcation. Primary 05C65, 15A69; Secondary 13P15, 14M99.

Key words and phrases. Hypergraph; trace; Estrada index; adjacency tensor; eigenvalue.

*The corresponding author. This work was supported by National Natural Science Foundation of China (Grant

No. 11871073).

arXiv:2210.03311v1 [math.CO] 7 Oct 2022

2 Y.-Z. FAN, J. ZHENG, AND Y. YANG

Txm−1deﬁned by

(Txm−1)i=X

i2,...,im∈[n]

tii2...imxi2· · · xim, i ∈[n],

where x= (x1, . . . , xn)>. Using the traces deﬁned by Morozov and Shakirov [33], the d-th trace

Trd(T) of Tis expressed as follow:

(1.1) Trd(T)=(m−1)n−1X

d1+···+dn=d,

di∈N,i∈[n]

i=1

(di(m−1))! 

X

yi∈[n]m−1

tiyi

∂

∂aiyi



Tr(Ad(m−1)),

where A= (aij) be an n×nauxiliary matrix by taking all aij’s as variables, tiyi=tii2...imand

∂

∂aiyi=∂

∂aii2· · · ∂

∂aiimif yi= (i2, . . . , im).

The traces of a tensor are closely related to its eigenvalues, which were introduced by Lim [29]

and Qi [35] as follows, where I= (ii1i2...im) is the identity tensor of order mand dimension n,

namely, ii1i2...im= 1 if i1=i2=· · · =im∈[n] and ii1i2...im= 0 otherwise.

Deﬁnition 1.2. ( [29, 35]) Let Tbe an m-th order n-dimensional tensor. For some λ∈C, if

the polynomial system (λI − T )xm−1= 0, or equivalently Txm−1=λx[m−1], has a solution

x∈Cn\{0}, then λis called an eigenvalue of Tand xis an eigenvector of Tassociated with λ,

where x[m−1] := (xm−1

1, xm−1

2, . . . , xm−1

n).

The determinant det Tof Tis deﬁned to be the resultant of the polynomials Txm−1[25], and

the characteristic polynomial of Tis deﬁned to be ϕT(λ) := det(λI − T ) [4, 35]. It is known that

λis an eigenvalue of Tif and only if it is a root of ϕT(λ). The spectrum of Tis the multi-set of

the roots of ϕT(λ).

Morozov and Shakirov proved that

(1.2) det(I − T ) = exp ∞

d=1

−Trd(T)

d!=

∞

d=0

Pd−Tr1(T)

1,· · · ,−Trd(T)

d,

where Pd(the dth Schur polynomial) is deﬁned as P0= 1, and for d > 0,

Pd(t1, . . . , td) =

`=1 X

d1+···+d`=d,di∈Z+,i∈[`]

td1· · · td`

`!.

From Eq. (1.2), we can get the determinant det Tand the characteristic polynomial ϕT(λ) =

det(λI − T ) in terms of traces by considering the degree of the resultant; see [7, 36] for details.

Cooper and Dulte [7] gave explicit formulas for some low co-degree coeﬃcients of the charac-

teristic polynomial of A(H) of a uniform hypergraph H. Shao, Qi and Hu [36] provided a graph

interpretation for the d-th trace of a general tensor, and proved that

(1.3) Trd(T) =

i=1

λd

TRACE OF HYPERGRAPH 3

which is consistent with the matrix case, where λ1, . . . , λNare all eigenvalues of T, and N=

n(m−1)n−1.

The d-th trace of a uniform hypergraph H, denoted by Trd(H), is deﬁned to be Trd(A(H)).

Clark and Cooper [6] generalized the Harary-Sachs theorem of graphs to uniform hypergraphs

by expressing the trace as a weighted sum over a family of Veblen hypergraphs. Chen, Bu and

Zhou [5] gave a formula for the spectral moments (equivalently the traces) of a hypertree in terms

of the number of sub-hypertrees.

The traces of a hypergraph are also related to the Estrada index of the hypergraph, which was

recently introduced by Sun, Zhou and Bu [37].

Deﬁnition 1.3. ( [37]) Let Hbe an m-uniform hypergraph on nvertices, and let λ1, . . . , λNbe

all eigenvalues of the adjacency tensor A(H) of H, where N=n(m−1)n−1. The Estrada index of

His deﬁned to be

EE(H) =

i=1

eλi.

By Eq. (1.3), it is easily seen that

EE(H) =

∞

d=0

T rd(H)

d!.

When m= 2, the Estrada index in Deﬁnition 1.3 is exactly that of a graph, which was ﬁrst

introduced by Estrada [14] in 2000 and found useful in measuring the degree of protein folding [13]

and the centrality of complex networks [12]. So the Estrada index of hypergraphs may has potential

applications in networks modelled as hypergraphs. Pe˜na, Gutman and Rada [34] conjectured that

the path is the unique graph with the minimum Estrada index among all graphs (trees) with given

order, and the star is the unique one with the maximum Estrada index among all trees with given

order. The conjecture was partly proved by Das and Lee [8], and completely proved by Deng [9].

The other versions of Estrada index of hypergraphs were also investigated by Duan, Dam and

Wang [11] via signless Laplacian tensor or Laplacian tensor, and Lu, Xue and Zhu [32] via signless

Laplacian matrix. Recently, Fan et al. [21] proved that among all hypertrees with ﬁxed number

of edges, the hyperpath is the unique one with minimum Estrada index and the hyperstar is the

unique one with maximum Estrada index, which provided a hypergraph version of the result of

Pe˜na-Gutman-Rada conjecture.

We shall note here the development of spectral hypergraph theory. Since the Perron-Frobenius

theorem of nonnegative matrices was generalized to nonnegative tensors [3,23,39–41], the spectral

hypergraph theory develops rapidly on many topics, such as the spectral radius [2, 19, 24, 27,

28, 30, 31], the eigenvariety [15, 17, 20], the spectral symmetry [16, 18, 36, 43], the eigenvalues of

hypertrees [42].

In this paper, we will give new expressions of the traces of uniform hypergraphs, especially

for hypertrees and unicyclic hypergraphs, and provide some perturbation results for the traces of

4 Y.-Z. FAN, J. ZHENG, AND Y. YANG

a hypergraph when its structure is locally changed. As an application of the trace results, we

determine the unique hypertree with maximum Estrada index among all hypertrees with ﬁxed

number of edges and perfect matching. We characterize the linear unicyclic hypergraphs with

maximum Estrada index among all unicyclic hypergraphs with ﬁxed number of edges and given

girth, and particularly determine with maximum Estrada index among all unicyclic hypergraphs

with ﬁxed number of edges and girth 3.

2. Preliminaries

2.1. Tensors and hypergraphs. Atensor (also called hypermatrix )T= (ti1i2...im) of order m

and dimension nover Crefers to a multiarray of entries ti1i2...im∈Cfor all ij∈[n] := {1,2, . . . , n}

and j∈[m], which can be viewed to be the coordinates of the classical tensor (as a multilinear

function) under a certain basis. Surely, if m= 2, then Tis a matrix of size n×n.

Let Hbe a hypergraph. His called trival if it contains only one vertex; otherwise, it is called

nontrivial.His called linear if any two diﬀerent edges intersect into at most one vertex. Let

v∈V(H), and let Ev(H) denote the set of edges of Hthat contains the vertex v. The degree

dv(H) of vin His the cardinality of Ev(H). A vertex vof His called a cored vertex if it has degree

one. An edge eof His called a pendent edge if it contains |e| − 1 cored vertices. A walk Win His

a sequence of alternate vertices and edges: v0e1v1e2· · · elvl, where vi6=vi+1 and {vi, vi+1} ⊆ eifor

i= 0,1, . . . , l −1. If v0=vl, then Wis called a circuit, and is called a cycle if no vertices or edges

are repeated except v0=vl. The hypergraph His said to be connected if every two vertices are

connected by a walk; His called a hypertree if it is connected and acyclic, and is called unicyclic

if it contains exactly one cycle.

Amatching Mof His a set of vertex-disjoint edges of H, and Mis called a perfect matching

of Hif it covers all vertices of H. A multi-hypergraph is a hypergraph allowed to have multiple

edges, and is called m-valent if each vertex has degree of multiple of m. A Veblen hypergraph

is an m-uniform and m-valent multi-hypergraph. Throughout of this paper, all hypergraphs are

consider simple unless stated somewhere.

Hu, Qi and Shao [26] introduced a class of hypergraphs which are constructed from simple

graph.

Deﬁnition 2.1. ( [26]) Let G= (V(G), E(G)) be a graph with vertex set V=V(G) and edge set

E=E(G). For an integer m≥3, the m-th power of G, denoted by Gm:= (Vm, Em), is deﬁned

to be the m-uniform hypergraph with vertex set Vm=V∪ {ie,1, . . . , ie,m−2:e∈E}and edge set

Em={e∪ {ie,1, . . . , ie,m−2}:e∈E}, where ie,1, . . . , ie,m−2are new vertices inserted to each edge

e∈E(G).

By Deﬁnition 2.1, the power Tmof a tree Tis a hypertree, and the power Umof a unicyclic

graph Uis a linear unicyclic hypergraph. Denote Pn, Cn, Snrespectively a path, a cycle and a star

all with nedges (as simple graphs). Then Cm

nis a linear cycle as hypergraph, and Pm

nis called

TRACE OF HYPERGRAPH 5

ahyperpath, and Sm

nis called a hyperstar. The center of Snor Sm

nis the vertex with maximum

degree.

2.2. Traces of hypergraphs. Shao, Qi and Hu [36] gave a graph interpretation for the d-th trace

Trd(T). Let

Fd={((i1, α1),...,(id, αd)) : i1≤ · · · ≤ id, αj∈[n]m−1},

where ijis called the primary index (or root) of the m-tuple fj:= (ij, αj) for j∈[d]. Deﬁne an

ij-rooted directed star for the tuple fj:

Sfj(ij)=(Vj,{(ij, uk) : k= 1, . . . , m −1}),

where Vj={ij, u1, . . . , um−1}is considered as a set by omitting multiple indices if αj= (u1, . . . , um−1).

So we get a multi-directed graph associated with F, denoted and deﬁned as

R(F) = ∪d

j=1Sfj(ij).

Denote by b(F) the product of the factorial of the multiplicities of all arcs of R(F), c(F) the

product of the factorial of the outdegree of the all vertices of R(F), and W(F) the set of vertex

sequences of all Euler tours of R(F). Shao, Qi and Hu [36] proved that

(2.1) Trd(T)=(m−1)n−1X

F∈Fd

b(F)

c(F)πF(T)|W(F)|,

where πF(T) = Qd

i=1 tij,αjif F= ((i1, α1),...,(id, αd)).

Let Hbe an m-uniform hypergraph on nvertices and let A(H) be the adjacency tensor of H.

Given an ordering of the vertices of H, let

Fd(H) := {(e1(v1), . . . , ed(vd)) : ei∈E(H), v1≤ · · · ≤ vd},

be the set of d-tuples of ordered rooted edges, where ei(vi) is an edge eiwith root of vi∈eifor

i∈[d]. Deﬁne a rooted directed star Sei(vi)=(ei,{(vi, u) : u∈ei\{vi}}) for each i∈[d], and

multi-directed graph R(F) = Sd

i=1 Sei(vi) associated with F∈ Fd(H). Let

F

d(H) := {F∈ Fd(H) : R(F)is Eulerian}.

For an F∈ F

d(H), denote V(F) := V(R(F)), rv(F) the number of edges in Fwith vas the root,

and d+

v(F)=(m−1)rv(F) (namely, the outdegree of vin R(F)). Denote by τ(F) := τu(R(F)) the

number of arborescences of R(F) with root u(namely, a directed u-rooted spanning tree such that

all vertices except uhas a directed path from itself to u), which is equal to the principal minor of

the Laplacian matrix L(R(F)) of R(F) by deleting the row and column indexed by u[1, 38]. As

R(F) is Eulerian, τu(R(F)) is independent of the choice of the root uso that the root uis omitted.

Fan et al. [21] give an expression of the d-th trace of Has follows.

Lemma 2.2 ( [21]).For an m-uniform hypergraph Hon nvertices,

T rd(H) = d(m−1)nX

F∈F

d(H)

τ(F)

Qv∈V(F)d+

v(F).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

THETRACEOFUNIFORMHYPERGRAPHSWITHAPPLICATIONTOESTRADAINDEXYI-ZHENGFAN*,JIANZHENG,ANDYAYANGAbstract.Inthispaperweinvestigatethetracesoftheadjacencytensorofhypergraphs(simplycalledthetracesofhypergraphs).Wegivenewexpressionsforthetracesofhypertreesandlinearunicyclichypergraphsbytheweightfunctionassigne...

展开>> 收起<<

THE TRACE OF UNIFORM HYPERGRAPHS WITH APPLICATION TO ESTRADA INDEX YI-ZHENG FAN JIAN ZHENG AND YA YANG.pdf

共27页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

THE TRACE OF UNIFORM HYPERGRAPHS WITH APPLICATION TO ESTRADA INDEX YI-ZHENG FAN JIAN ZHENG AND YA YANG

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: