Hamiltonicity of Bell and Stirling colour graphs
Utilitas Mathematica · 12.05.2026 · 127 · 239-258
DOI: 10.61091/um127-16 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 12.05.2026. Verfasst von S. Finbow und 1 weiteren Autor:innen.
Abstract (Originalsprache)
For a graph \(G\) and a positive integer \(k\), the \(k\)-Bell colour graph of \(G\) is the graph whose vertices are the partitions of \(V\) into at most \(k\) independent sets, with two of these being adjacent if there exists a vertex \(x\) such that the partitions are identical when restricted to \(V - \{x\}\). The \(k\)-Stirling colour graph of \(G\) is defined similarly, but for partitions into exactly \(k\) independent sets. Building on the existing result that for each \(k \geq 3\), the \(k\)-Bell colour graph of a tree with at least 4 vertices is Hamiltonian, we show that every graph on \(n\) vertices, except \(K_n\) and \(K_n - e\), has a Hamiltonian \(n\)-Bell colour graph, and this result is best possible. It is also shown that, for \(k \geq 4\), the \(k\)-Stirling colour graph of a tree with at least \(k+1\) vertices is Hamiltonian.
Zitieren
APA
Finbow, S., & MacGillivray, G. (2026). Hamiltonicity of Bell and Stirling colour graphs. Utilitas Mathematica, 127, 239-258. https://doi.org/10.61091/um127-16
Vancouver
Finbow S, MacGillivray G. Hamiltonicity of Bell and Stirling colour graphs. Utilitas Mathematica. 2026;127:239-258. doi:10.61091/um127-16
BibTeX
@article{Finbow2026,
author = {Finbow, S. and MacGillivray, G.},
title = {Hamiltonicity of Bell and Stirling colour graphs},
journal = {Utilitas Mathematica},
year = {2026},
volume = {127},
pages = {239--258},
doi = {10.61091/um127-16}
}
EUVIMED