On the minimum spectral radius of connected graphs of given order and size Article Swipe

PDF

Sebastian M. Cioabă , Vishal Gupta , Celso Marques ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2405.15046

In this paper, we study a question of Hong from 1993 related to the minimum spectral radii of the adjacency matrices of connected graphs of given order and size. Hong asked if it is true that among all connected graphs of given number of vertices $n$ and number of edges $e$, the graphs having minimum spectral radius (the minimizer graphs) must be almost regular, meaning that the difference between their maximum degree and their minimum degree is at most one. In this paper, we answer Hong's question positively for various values of $n$ and $e$ and in several cases, we determined the graphs with minimum spectral radius.

Related Topics

Concepts

Spectral radius Order (exchange) RADIUS Mathematics Combinatorics Physics Computer science Business Quantum mechanics Computer network Eigenvalues and eigenvectors Finance

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2405.15046
PDF: https://arxiv.org/pdf/2405.15046
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4399061796

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4399061796

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2405.15046

Digital Object Identifier
Title: On the minimum spectral radius of connected graphs of given order and size

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-05-23

Full publication date if available
Authors: Sebastian M. Cioabă, Vishal Gupta, Celso Marques

List of authors in order
Landing page: https://arxiv.org/abs/2405.15046

Publisher landing page
PDF URL: https://arxiv.org/pdf/2405.15046

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2405.15046

Direct OA link when available
Concepts: Spectral radius, Order (exchange), RADIUS, Mathematics, Combinatorics, Physics, Computer science, Business, Quantum mechanics, Computer network, Eigenvalues and eigenvectors, Finance

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4399061796
doi	https://doi.org/10.48550/arxiv.2405.15046
ids.doi	https://doi.org/10.48550/arxiv.2405.15046
ids.openalex	https://openalex.org/W4399061796
fwci
type	preprint
title	On the minimum spectral radius of connected graphs of given order and size
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C140532419
concepts[0].level	3
concepts[0].score	0.6949279308319092
concepts[0].wikidata	https://www.wikidata.org/wiki/Q249748
concepts[0].display_name	Spectral radius
concepts[1].id	https://openalex.org/C182306322
concepts[1].level	2
concepts[1].score	0.6780632138252258
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1779371
concepts[1].display_name	Order (exchange)
concepts[2].id	https://openalex.org/C178635117
concepts[2].level	2
concepts[2].score	0.6320878863334656
concepts[2].wikidata	https://www.wikidata.org/wiki/Q747499
concepts[2].display_name	RADIUS
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.5007314682006836
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C114614502
concepts[4].level	1
concepts[4].score	0.4768482446670532
concepts[4].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[4].display_name	Combinatorics
concepts[5].id	https://openalex.org/C121332964
concepts[5].level	0
concepts[5].score	0.29882436990737915
concepts[5].wikidata	https://www.wikidata.org/wiki/Q413
concepts[5].display_name	Physics
concepts[6].id	https://openalex.org/C41008148
concepts[6].level	0
concepts[6].score	0.27501848340034485
concepts[6].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[6].display_name	Computer science
concepts[7].id	https://openalex.org/C144133560
concepts[7].level	0
concepts[7].score	0.1287021040916443
concepts[7].wikidata	https://www.wikidata.org/wiki/Q4830453
concepts[7].display_name	Business
concepts[8].id	https://openalex.org/C62520636
concepts[8].level	1
concepts[8].score	0.09331762790679932
concepts[8].wikidata	https://www.wikidata.org/wiki/Q944
concepts[8].display_name	Quantum mechanics
concepts[9].id	https://openalex.org/C31258907
concepts[9].level	1
concepts[9].score	0.06636360287666321
concepts[9].wikidata	https://www.wikidata.org/wiki/Q1301371
concepts[9].display_name	Computer network
concepts[10].id	https://openalex.org/C158693339
concepts[10].level	2
concepts[10].score	0.04373359680175781
concepts[10].wikidata	https://www.wikidata.org/wiki/Q190524
concepts[10].display_name	Eigenvalues and eigenvectors
concepts[11].id	https://openalex.org/C10138342
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q43015
concepts[11].display_name	Finance
keywords[0].id	https://openalex.org/keywords/spectral-radius
keywords[0].score	0.6949279308319092
keywords[0].display_name	Spectral radius
keywords[1].id	https://openalex.org/keywords/order
keywords[1].score	0.6780632138252258
keywords[1].display_name	Order (exchange)
keywords[2].id	https://openalex.org/keywords/radius
keywords[2].score	0.6320878863334656
keywords[2].display_name	RADIUS
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.5007314682006836
keywords[3].display_name	Mathematics
keywords[4].id	https://openalex.org/keywords/combinatorics
keywords[4].score	0.4768482446670532
keywords[4].display_name	Combinatorics
keywords[5].id	https://openalex.org/keywords/physics
keywords[5].score	0.29882436990737915
keywords[5].display_name	Physics
keywords[6].id	https://openalex.org/keywords/computer-science
keywords[6].score	0.27501848340034485
keywords[6].display_name	Computer science
keywords[7].id	https://openalex.org/keywords/business
keywords[7].score	0.1287021040916443
keywords[7].display_name	Business
keywords[8].id	https://openalex.org/keywords/quantum-mechanics
keywords[8].score	0.09331762790679932
keywords[8].display_name	Quantum mechanics
keywords[9].id	https://openalex.org/keywords/computer-network
keywords[9].score	0.06636360287666321
keywords[9].display_name	Computer network
keywords[10].id	https://openalex.org/keywords/eigenvalues-and-eigenvectors
keywords[10].score	0.04373359680175781
keywords[10].display_name	Eigenvalues and eigenvectors
language	en
locations[0].id	pmh:oai:arXiv.org:2405.15046
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2405.15046
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2405.15046
locations[1].id	doi:10.48550/arxiv.2405.15046
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article-journal
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2405.15046
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5002085058
authorships[0].author.orcid	https://orcid.org/0000-0001-9983-0212
authorships[0].author.display_name	Sebastian M. Cioabă
authorships[0].author_position	first
authorships[0].raw_author_name	Cioabă, Sebastian M.
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5100602164
authorships[1].author.orcid	https://orcid.org/0000-0003-3574-1805
authorships[1].author.display_name	Vishal Gupta
authorships[1].author_position	middle
authorships[1].raw_author_name	Gupta, Vishal
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5102677573
authorships[2].author.orcid
authorships[2].author.display_name	Celso Marques
authorships[2].author_position	last
authorships[2].raw_author_name	Marques, Celso
authorships[2].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://arxiv.org/pdf/2405.15046
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	On the minimum spectral radius of connected graphs of given order and size
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic
related_works	https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2107559391, https://openalex.org/W2278418704, https://openalex.org/W2350512268
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2405.15046
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2405.15046
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2405.15046
primary_location.id	pmh:oai:arXiv.org:2405.15046
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2405.15046
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2405.15046
publication_date	2024-05-23
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	5
abstract_inverted_index.In	0, 80
abstract_inverted_index.at	77
abstract_inverted_index.be	61
abstract_inverted_index.if	31
abstract_inverted_index.in	96
abstract_inverted_index.is	33, 76
abstract_inverted_index.it	32
abstract_inverted_index.of	7, 17, 21, 24, 40, 43, 48, 91
abstract_inverted_index.to	12
abstract_inverted_index.we	3, 83, 99
abstract_inverted_index.$e$	94
abstract_inverted_index.$n$	45, 92
abstract_inverted_index.all	37
abstract_inverted_index.and	27, 46, 72, 93, 95
abstract_inverted_index.for	88
abstract_inverted_index.the	13, 18, 51, 66, 101
abstract_inverted_index.$e$,	50
abstract_inverted_index.(the	57
abstract_inverted_index.1993	10
abstract_inverted_index.Hong	8, 29
abstract_inverted_index.from	9
abstract_inverted_index.most	78
abstract_inverted_index.must	60
abstract_inverted_index.one.	79
abstract_inverted_index.that	35, 65
abstract_inverted_index.this	1, 81
abstract_inverted_index.true	34
abstract_inverted_index.with	103
abstract_inverted_index.among	36
abstract_inverted_index.asked	30
abstract_inverted_index.edges	49
abstract_inverted_index.given	25, 41
abstract_inverted_index.order	26
abstract_inverted_index.radii	16
abstract_inverted_index.size.	28
abstract_inverted_index.study	4
abstract_inverted_index.their	69, 73
abstract_inverted_index.Hong's	85
abstract_inverted_index.almost	62
abstract_inverted_index.answer	84
abstract_inverted_index.cases,	98
abstract_inverted_index.degree	71, 75
abstract_inverted_index.graphs	23, 39, 52, 102
abstract_inverted_index.having	53
abstract_inverted_index.number	42, 47
abstract_inverted_index.paper,	2, 82
abstract_inverted_index.radius	56
abstract_inverted_index.values	90
abstract_inverted_index.between	68
abstract_inverted_index.graphs)	59
abstract_inverted_index.maximum	70
abstract_inverted_index.meaning	64
abstract_inverted_index.minimum	14, 54, 74, 104
abstract_inverted_index.radius.	106
abstract_inverted_index.related	11
abstract_inverted_index.several	97
abstract_inverted_index.various	89
abstract_inverted_index.matrices	20
abstract_inverted_index.question	6, 86
abstract_inverted_index.regular,	63
abstract_inverted_index.spectral	15, 55, 105
abstract_inverted_index.vertices	44
abstract_inverted_index.adjacency	19
abstract_inverted_index.connected	22, 38
abstract_inverted_index.minimizer	58
abstract_inverted_index.determined	100
abstract_inverted_index.difference	67
abstract_inverted_index.positively	87
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile