Algorithmic approach to obtaining values of (k,g)-spectra

13.11.2024 10:15 - 11:00

Dominika Závacká (Comenius University, Bratislava)

A \((k,g)\)-graph is a \(k\)-regular graph of girth \(g\). The \((k,g)\)-spectrum is the set of all possible orders of \((k,g)\)-graphs for a specific degree/girth pair \((k,g)\). The smallest order in the \((k,g)\)-spectrum corresponds to the order \(n(k,g)\) of a \((k,g)\)-cage, which is a graph of the smallest order among all \((k,g)\)-graphs. The value \(n(k,g)\) is unknown and difficult to determine for most parameter pairs \((k,g)\), and the general problem of determining these values for all parameter pairs \((k,g)\) is the well-known Cage Problem. In our talk, we will present various methods for identifying orders contained in the \((k,g)\)-spectra; which is equivalent to proving the existence or constructing \((k,g)\)-graphs of prescribed orders. It is interesting to note that a \((k,g)\)-spectrum is not always continuous; for instance, the (3,8)-spectrum contains values 30 and 34, but lacks the order 32; as it has been computationally proven that no (3,8)-graph of order 32 exists. To address this, we define and compute \(N(k,g)\), the smallest order from which a \((k,g)\)-graph of every larger order is guaranteed to exist. As determining the smallest value \(n(k,g)\) of a \((k, g)\)-spectrum is a computationally hard problem, we focus on cases where the minimal order \(n(k,g)\) (the order of a \((k,g)\)-cage) is already known. Despite the challenges of establishing the full \((k,g)\)-spectra for general pairs \((k,g)\), we provide both complete and partial computation results for several parameter pairs \((k,g)\).

Organiser:

G. Arzhantseva, Ch. Cashen

Location:
SR 06, OG 1., OMP1