Edge-disjoint spanning trees and balloons in (multi-)graphs from size or spectral radius Article Swipe
Kun Cheng
,
Zihan Zhou
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.13001/ela.2025.8673
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.13001/ela.2025.8673
A multigraph is a graph that may have multiple edges, but has no loops. The multiplicity of a multigraph is the maximum number of edges between any pair of vertices. The spanning tree packing number of a graph $G$, denoted by $\tau(G)$, is the maximum number of edge-disjoint spanning trees contained in $G$. A balloon of a graph $G$ is a maximal 2-edge-connected subgraph that is joined to the rest of $G$ by exactly one cut edge. By $b(G)$, $e(G)$, and $\kappa(G)$, we denote the number of balloons, the size, and the vertex-connectivity of $G$, respectively. In this paper, we show that for a positive integer $k$ and any multigraph $G$ of order $n\geq 2r$ with multiplicity $m\leq k$ and minimum degree $\delta \geq2k$, if $e(G)\geq m[\binom{r}{2}+\binom{n-r}{2}]+k,$ then $\tau(G)\geq k$, where $r=\lceil(\delta+1)/m\rceil$. This extends the result of Fan, Gu and Lin (J. Graph Theory, 2023). Analogous results involving the size to characterize $\kappa(G)\geq k$ or $b(G)\leq k-1$ of a multigraph $G$ are also presented. In addition, we prove a tight sufficient condition to guarantee $b(G)\leq k-1$ in terms of the spectral radius of a simple graph $G$, with extremal graphs characterized.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.13001/ela.2025.8673
- OA Status
- diamond
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4413213770
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4413213770Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.13001/ela.2025.8673Digital Object Identifier
- Title
-
Edge-disjoint spanning trees and balloons in (multi-)graphs from size or spectral radiusWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-08-11Full publication date if available
- Authors
-
Kun Cheng, Zihan ZhouList of authors in order
- Landing page
-
https://doi.org/10.13001/ela.2025.8673Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
diamondOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.13001/ela.2025.8673Direct OA link when available
- Concepts
-
Multigraph, Combinatorics, Mathematics, Disjoint sets, Multiplicity (mathematics), Spectral radius, Vertex (graph theory), Spanning tree, Graph, Connectivity, Simple graph, Discrete mathematics, Eigenvalues and eigenvectors, Geometry, Physics, Quantum mechanicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4413213770 |
|---|---|
| doi | https://doi.org/10.13001/ela.2025.8673 |
| ids.doi | https://doi.org/10.13001/ela.2025.8673 |
| ids.openalex | https://openalex.org/W4413213770 |
| fwci | 0.0 |
| type | article |
| title | Edge-disjoint spanning trees and balloons in (multi-)graphs from size or spectral radius |
| biblio.issue | |
| biblio.volume | 41 |
| biblio.last_page | 451 |
| biblio.first_page | 436 |
| topics[0].id | https://openalex.org/T11476 |
| topics[0].field.id | https://openalex.org/fields/26 |
| topics[0].field.display_name | Mathematics |
| topics[0].score | 0.9994999766349792 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2608 |
| topics[0].subfield.display_name | Geometry and Topology |
| topics[0].display_name | Graph theory and applications |
| topics[1].id | https://openalex.org/T10829 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9976000189781189 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Interconnection Networks and Systems |
| topics[2].id | https://openalex.org/T10374 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9800000190734863 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Advanced Graph Theory Research |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C17758045 |
| concepts[0].level | 3 |
| concepts[0].score | 0.9368087649345398 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q2642629 |
| concepts[0].display_name | Multigraph |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.9079349637031555 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.8218921422958374 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C45340560 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5895898938179016 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q215382 |
| concepts[3].display_name | Disjoint sets |
| concepts[4].id | https://openalex.org/C156004811 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5440442562103271 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2228257 |
| concepts[4].display_name | Multiplicity (mathematics) |
| concepts[5].id | https://openalex.org/C140532419 |
| concepts[5].level | 3 |
| concepts[5].score | 0.5425854325294495 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q249748 |
| concepts[5].display_name | Spectral radius |
| concepts[6].id | https://openalex.org/C80899671 |
| concepts[6].level | 3 |
| concepts[6].score | 0.5378867983818054 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[6].display_name | Vertex (graph theory) |
| concepts[7].id | https://openalex.org/C64331007 |
| concepts[7].level | 2 |
| concepts[7].score | 0.5134792923927307 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q831672 |
| concepts[7].display_name | Spanning tree |
| concepts[8].id | https://openalex.org/C132525143 |
| concepts[8].level | 2 |
| concepts[8].score | 0.5091895461082458 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[8].display_name | Graph |
| concepts[9].id | https://openalex.org/C76444178 |
| concepts[9].level | 3 |
| concepts[9].score | 0.4387398660182953 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q72897900 |
| concepts[9].display_name | Connectivity |
| concepts[10].id | https://openalex.org/C2993105083 |
| concepts[10].level | 3 |
| concepts[10].score | 0.42516207695007324 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[10].display_name | Simple graph |
| concepts[11].id | https://openalex.org/C118615104 |
| concepts[11].level | 1 |
| concepts[11].score | 0.41814666986465454 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[11].display_name | Discrete mathematics |
| concepts[12].id | https://openalex.org/C158693339 |
| concepts[12].level | 2 |
| concepts[12].score | 0.15029022097587585 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q190524 |
| concepts[12].display_name | Eigenvalues and eigenvectors |
| concepts[13].id | https://openalex.org/C2524010 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0951155424118042 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[13].display_name | Geometry |
| concepts[14].id | https://openalex.org/C121332964 |
| concepts[14].level | 0 |
| concepts[14].score | 0.08068755269050598 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[14].display_name | Physics |
| concepts[15].id | https://openalex.org/C62520636 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[15].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/multigraph |
| keywords[0].score | 0.9368087649345398 |
| keywords[0].display_name | Multigraph |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.9079349637031555 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.8218921422958374 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/disjoint-sets |
| keywords[3].score | 0.5895898938179016 |
| keywords[3].display_name | Disjoint sets |
| keywords[4].id | https://openalex.org/keywords/multiplicity |
| keywords[4].score | 0.5440442562103271 |
| keywords[4].display_name | Multiplicity (mathematics) |
| keywords[5].id | https://openalex.org/keywords/spectral-radius |
| keywords[5].score | 0.5425854325294495 |
| keywords[5].display_name | Spectral radius |
| keywords[6].id | https://openalex.org/keywords/vertex |
| keywords[6].score | 0.5378867983818054 |
| keywords[6].display_name | Vertex (graph theory) |
| keywords[7].id | https://openalex.org/keywords/spanning-tree |
| keywords[7].score | 0.5134792923927307 |
| keywords[7].display_name | Spanning tree |
| keywords[8].id | https://openalex.org/keywords/graph |
| keywords[8].score | 0.5091895461082458 |
| keywords[8].display_name | Graph |
| keywords[9].id | https://openalex.org/keywords/connectivity |
| keywords[9].score | 0.4387398660182953 |
| keywords[9].display_name | Connectivity |
| keywords[10].id | https://openalex.org/keywords/simple-graph |
| keywords[10].score | 0.42516207695007324 |
| keywords[10].display_name | Simple graph |
| keywords[11].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[11].score | 0.41814666986465454 |
| keywords[11].display_name | Discrete mathematics |
| keywords[12].id | https://openalex.org/keywords/eigenvalues-and-eigenvectors |
| keywords[12].score | 0.15029022097587585 |
| keywords[12].display_name | Eigenvalues and eigenvectors |
| keywords[13].id | https://openalex.org/keywords/geometry |
| keywords[13].score | 0.0951155424118042 |
| keywords[13].display_name | Geometry |
| keywords[14].id | https://openalex.org/keywords/physics |
| keywords[14].score | 0.08068755269050598 |
| keywords[14].display_name | Physics |
| language | en |
| locations[0].id | doi:10.13001/ela.2025.8673 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S121701187 |
| locations[0].source.issn | 1081-3810, 1537-9582 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 1081-3810 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Electronic Journal of Linear Algebra |
| locations[0].source.host_organization | |
| locations[0].source.host_organization_name | |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | The Electronic Journal of Linear Algebra |
| locations[0].landing_page_url | https://doi.org/10.13001/ela.2025.8673 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5104083138 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-1447-1845 |
| authorships[0].author.display_name | Kun Cheng |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Kun Cheng |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5016719769 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-0081-5675 |
| authorships[1].author.display_name | Zihan Zhou |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Zihan Zhou |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doi.org/10.13001/ela.2025.8673 |
| open_access.oa_status | diamond |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Edge-disjoint spanning trees and balloons in (multi-)graphs from size or spectral radius |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T11476 |
| primary_topic.field.id | https://openalex.org/fields/26 |
| primary_topic.field.display_name | Mathematics |
| primary_topic.score | 0.9994999766349792 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2608 |
| primary_topic.subfield.display_name | Geometry and Topology |
| primary_topic.display_name | Graph theory and applications |
| related_works | https://openalex.org/W2066285211, https://openalex.org/W3033646691, https://openalex.org/W2124312028, https://openalex.org/W2530398396, https://openalex.org/W1988736474, https://openalex.org/W2024593554, https://openalex.org/W2065218154, https://openalex.org/W2298713664, https://openalex.org/W2964243625, https://openalex.org/W4322716708 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.13001/ela.2025.8673 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S121701187 |
| best_oa_location.source.issn | 1081-3810, 1537-9582 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 1081-3810 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Electronic Journal of Linear Algebra |
| best_oa_location.source.host_organization | |
| best_oa_location.source.host_organization_name | |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | The Electronic Journal of Linear Algebra |
| best_oa_location.landing_page_url | https://doi.org/10.13001/ela.2025.8673 |
| primary_location.id | doi:10.13001/ela.2025.8673 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S121701187 |
| primary_location.source.issn | 1081-3810, 1537-9582 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 1081-3810 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Electronic Journal of Linear Algebra |
| primary_location.source.host_organization | |
| primary_location.source.host_organization_name | |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | The Electronic Journal of Linear Algebra |
| primary_location.landing_page_url | https://doi.org/10.13001/ela.2025.8673 |
| publication_date | 2025-08-11 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 0, 53 |
| abstract_inverted_index.a | 3, 17, 36, 56, 60, 103, 158, 168, 183 |
| abstract_inverted_index.By | 77 |
| abstract_inverted_index.Gu | 138 |
| abstract_inverted_index.In | 96, 164 |
| abstract_inverted_index.by | 40, 72 |
| abstract_inverted_index.if | 124 |
| abstract_inverted_index.in | 51, 176 |
| abstract_inverted_index.is | 2, 19, 42, 59, 65 |
| abstract_inverted_index.k$ | 118, 153 |
| abstract_inverted_index.no | 12 |
| abstract_inverted_index.of | 16, 23, 28, 35, 46, 55, 70, 86, 93, 111, 136, 157, 178, 182 |
| abstract_inverted_index.or | 154 |
| abstract_inverted_index.to | 67, 150, 172 |
| abstract_inverted_index.we | 82, 99, 166 |
| abstract_inverted_index.$G$ | 58, 71, 110, 160 |
| abstract_inverted_index.$k$ | 106 |
| abstract_inverted_index.(J. | 141 |
| abstract_inverted_index.2r$ | 114 |
| abstract_inverted_index.Lin | 140 |
| abstract_inverted_index.The | 14, 30 |
| abstract_inverted_index.and | 80, 90, 107, 119, 139 |
| abstract_inverted_index.any | 26, 108 |
| abstract_inverted_index.are | 161 |
| abstract_inverted_index.but | 10 |
| abstract_inverted_index.cut | 75 |
| abstract_inverted_index.for | 102 |
| abstract_inverted_index.has | 11 |
| abstract_inverted_index.k$, | 129 |
| abstract_inverted_index.may | 6 |
| abstract_inverted_index.one | 74 |
| abstract_inverted_index.the | 20, 43, 68, 84, 88, 91, 134, 148, 179 |
| abstract_inverted_index.$G$, | 38, 94, 186 |
| abstract_inverted_index.$G$. | 52 |
| abstract_inverted_index.Fan, | 137 |
| abstract_inverted_index.This | 132 |
| abstract_inverted_index.also | 162 |
| abstract_inverted_index.have | 7 |
| abstract_inverted_index.k-1$ | 156, 175 |
| abstract_inverted_index.pair | 27 |
| abstract_inverted_index.rest | 69 |
| abstract_inverted_index.show | 100 |
| abstract_inverted_index.size | 149 |
| abstract_inverted_index.that | 5, 64, 101 |
| abstract_inverted_index.then | 127 |
| abstract_inverted_index.this | 97 |
| abstract_inverted_index.tree | 32 |
| abstract_inverted_index.with | 115, 187 |
| abstract_inverted_index.Graph | 142 |
| abstract_inverted_index.edge. | 76 |
| abstract_inverted_index.edges | 24 |
| abstract_inverted_index.graph | 4, 37, 57, 185 |
| abstract_inverted_index.order | 112 |
| abstract_inverted_index.prove | 167 |
| abstract_inverted_index.size, | 89 |
| abstract_inverted_index.terms | 177 |
| abstract_inverted_index.tight | 169 |
| abstract_inverted_index.trees | 49 |
| abstract_inverted_index.where | 130 |
| abstract_inverted_index.$m\leq | 117 |
| abstract_inverted_index.$n\geq | 113 |
| abstract_inverted_index.2023). | 144 |
| abstract_inverted_index.degree | 121 |
| abstract_inverted_index.denote | 83 |
| abstract_inverted_index.edges, | 9 |
| abstract_inverted_index.graphs | 189 |
| abstract_inverted_index.joined | 66 |
| abstract_inverted_index.loops. | 13 |
| abstract_inverted_index.number | 22, 34, 45, 85 |
| abstract_inverted_index.paper, | 98 |
| abstract_inverted_index.radius | 181 |
| abstract_inverted_index.result | 135 |
| abstract_inverted_index.simple | 184 |
| abstract_inverted_index.$\delta | 122 |
| abstract_inverted_index.$b(G)$, | 78 |
| abstract_inverted_index.$e(G)$, | 79 |
| abstract_inverted_index.Theory, | 143 |
| abstract_inverted_index.balloon | 54 |
| abstract_inverted_index.between | 25 |
| abstract_inverted_index.denoted | 39 |
| abstract_inverted_index.exactly | 73 |
| abstract_inverted_index.extends | 133 |
| abstract_inverted_index.integer | 105 |
| abstract_inverted_index.maximal | 61 |
| abstract_inverted_index.maximum | 21, 44 |
| abstract_inverted_index.minimum | 120 |
| abstract_inverted_index.packing | 33 |
| abstract_inverted_index.results | 146 |
| abstract_inverted_index.\geq2k$, | 123 |
| abstract_inverted_index.extremal | 188 |
| abstract_inverted_index.multiple | 8 |
| abstract_inverted_index.positive | 104 |
| abstract_inverted_index.spanning | 31, 48 |
| abstract_inverted_index.spectral | 180 |
| abstract_inverted_index.subgraph | 63 |
| abstract_inverted_index.$b(G)\leq | 155, 174 |
| abstract_inverted_index.$e(G)\geq | 125 |
| abstract_inverted_index.Analogous | 145 |
| abstract_inverted_index.addition, | 165 |
| abstract_inverted_index.balloons, | 87 |
| abstract_inverted_index.condition | 171 |
| abstract_inverted_index.contained | 50 |
| abstract_inverted_index.guarantee | 173 |
| abstract_inverted_index.involving | 147 |
| abstract_inverted_index.vertices. | 29 |
| abstract_inverted_index.$\tau(G)$, | 41 |
| abstract_inverted_index.multigraph | 1, 18, 109, 159 |
| abstract_inverted_index.presented. | 163 |
| abstract_inverted_index.sufficient | 170 |
| abstract_inverted_index.$\kappa(G)$, | 81 |
| abstract_inverted_index.$\tau(G)\geq | 128 |
| abstract_inverted_index.characterize | 151 |
| abstract_inverted_index.multiplicity | 15, 116 |
| abstract_inverted_index.edge-disjoint | 47 |
| abstract_inverted_index.respectively. | 95 |
| abstract_inverted_index.$\kappa(G)\geq | 152 |
| abstract_inverted_index.characterized. | 190 |
| abstract_inverted_index.2-edge-connected | 62 |
| abstract_inverted_index.vertex-connectivity | 92 |
| abstract_inverted_index.$r=\lceil(\delta+1)/m\rceil$. | 131 |
| abstract_inverted_index.m[\binom{r}{2}+\binom{n-r}{2}]+k,$ | 126 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.37003583 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |