Decorated hub graphs and the number of cycle spectra of graphs

A graph’s cycle spectrum is the set of lengths of its cycles. In this paper, I improve my previous lower bound on the number of distinct cycle spectra of graphs on n vertices from 19.61 × 2^(n/2) to 37.18 × 2^(n/2) for every n ≥ 1024. Most of the improvement comes from attaching short paths to hub graphs and counting the distinct spectra they produce.This is all related to Erdos Problem 84 (see https://www.erdosproblems.com/84), which asks if f(n)/(2^(n/2)) approaches infinity, where f(n) denotes the number of distinct cycle spectra of graphs on n vertices.. From the research I've done thus far, I would lean that f(n)/(2^(n/2)) is bounded, but only slightly.If you find anything erroneous / want to contact me my email is eliasbot at usc.edu.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24356010
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Decorated hub graphs and the number of cycle spectra of graphs

Elias Botsford
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Decorated hub graphs and the number of cycle spectra of graphs

Elias Botsford
preprint en

Abstract

A graph’s cycle spectrum is the set of lengths of its cycles. In this paper, I improve my previous lower bound on the number of distinct cycle spectra of graphs on n vertices from 19.61 × 2^(n/2) to 37.18 × 2^(n/2) for every n ≥ 1024. Most of the improvement comes from attaching short paths to hub graphs and counting the distinct spectra they produce.This is all related to Erdos Problem 84 (see https://www.erdosproblems.com/84), which asks if f(n)/(2^(n/2)) approaches infinity, where f(n) denotes the number of distinct cycle spectra of graphs on n vertices.. From the research I've done thus far, I would lean that f(n)/(2^(n/2)) is bounded, but only slightly.If you find anything erroneous / want to contact me my email is eliasbot at usc.edu.

Zenodo (CERN European Organization for Nuclear Research)
University of Southern California (US)
Limits and Structures in Graph Theory
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