Sufficient conditions for spanning trees with bounded total excess

Let G be a connected graph and let k ≥ 2 be an integer. A spanning tree with maximum degree at most k is called a spanning k-tree. As a generalization of the above concept, the concept of total excess is defined as follows: for a spanning subgraph H of a connected graph G and an integer t, the total t-excess te(H,t) is defined by te(H,t) = X max{0,dH(v) − t}, v∈V(H) where dH(v) is the degree of v in H. It is easy to see that for a spanning tree T, T is a spanning k-tree if and only if te(T,t) = 0. Let e(G) and ρa(G) denote the size and the Aa-spectral radius of G, respectively. In this work, we put forward two sufficient conditions for a connected graph G containing a spanning tree T with te(T,k) ≤ k − 3 via the size or the Aa-spectral radius.

Authors

Publication Details

Journal
RAIRO - Operations Research
Published
2026-11-17
DOI
https://doi.org/10.1051/ro/2026123
Primary Topic
Graph theory and applications
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Sufficient conditions for spanning trees with bounded total excess

Sufang Wang
4 links
RAIRO - Operations Research
Graph theory and applications
article

Sufficient conditions for spanning trees with bounded total excess

Sufang Wang
article en

Abstract

Let G be a connected graph and let k ≥ 2 be an integer. A spanning tree with maximum degree at most k is called a spanning k-tree. As a generalization of the above concept, the concept of total excess is defined as follows: for a spanning subgraph H of a connected graph G and an integer t, the total t-excess te(H,t) is defined by te(H,t) = X max{0,dH(v) − t}, v∈V(H) where dH(v) is the degree of v in H. It is easy to see that for a spanning tree T, T is a spanning k-tree if and only if te(T,t) = 0. Let e(G) and ρa(G) denote the size and the Aa-spectral radius of G, respectively. In this work, we put forward two sufficient conditions for a connected graph G containing a spanning tree T with te(T,k) ≤ k − 3 via the size or the Aa-spectral radius.

RAIRO - Operations Research
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon