circulant graphs – Optimization Online

An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs

Published: 2026/08/19

Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming branch-and-cut, circulant graphs, combinatorial optimization, integer programming, ramsey numbers

The Ramsey number R(m,n) is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size m or a red clique of size n. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that … Read more

Isomorphism testing for circulant graphs Cn(a,b)

Published: 2010/03/22

Graphs and Matroids adam's conjecture, circulant graphs, isomorphism

In this paper we focus on connected directed/undirected circulant graphs Cn(a,b). We investigate some topological characteristics, and define a simple combinatorial model, which is new for the topic. Building on such a model, we derive a necessary and sufficient condition to test whether two circulant graphs Cn(a, b) and Cn(a’,b’) are isomorphic or not. The … Read more