Search the repository

Abstract: We describe here how the recent Wagner’s approach for applying reinforcement learning to construct examples in graph theory can be used in the search for critical graphs for small Ramsey numbers. We illustrate this application by providing lower bounds for the small Ramsey numbers R(K_{2, 5}, K_{3, 5}), R(B₃, B₆) and R(B₄, B₅) and by improving the lower known bound for R(W₅, W₇).
Keywords: Ramsey number, critical graph, reinforcement learning, cross-entropy method
Published in RUP: 03.11.2025; Views: 257; Downloads: 4
Full text (291,40 KB)

Abstract: While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph admits an eigenvector consisting solely of ▫$\pm 1$▫ entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ▫$\pm 1$▫ eigenvector is quite rich, being closed under a number of different graph compositions.
Keywords: eigenvector, adjacency matrix, Wilf's problem
Published in RUP: 03.01.2022; Views: 2357; Downloads: 33
Full text (325,02 KB)

Keywords: particija grafa, odkrivanje skupnosti, algoritem Kernighan-Lin, maksimalen prerez, spektralna particija, modularnost, enostavna maksimizacija modularnosti, spektralna maksimizacija modularnosti, bisekcija grafa, hierarhično grozdenje, hevristike, aproksimacijski algoritmi, dendrogram
Published in RUP: 13.11.2017; Views: 3870; Downloads: 62
Link to full text

Keywords: molecular descriptor, bond-additive descriptor, discrete Adriatic index
Published in RUP: 03.04.2017; Views: 3460; Downloads: 129
Link to full text

Keywords: hypergraph, hamiltonian cycle, decomposition, double generalized Petersen graph, automorphism group, vertex-transitive, sign graph, L-eigenvalue, lollipop graph
Published in RUP: 09.08.2016; Views: 4825; Downloads: 35
Link to full text