Hardness results and spectral techniques for combinatorial problems on circulant graphs

DOI10.1016/S0024-3795(98)10126-XzbMath0931.05050OpenAlexW2085648192WikidataQ126782319 ScholiaQ126782319MaRDI QIDQ1124798

Bruno Codenotti, Ivan Gerace, Sebastiano Vigna

Publication date: 28 November 1999

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0024-3795(98)10126-x

zbMATH Keywords

eigenvalueseigenvectorschromatic numbercliquecirculant matricescirculant graphsapproximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Dominator and total dominator coloring of circulant graph C_n(1, 2), The two-stripe symmetric circulant TSP is in P, Random cyclic triangle-free graphs of prime order, On CIS circulants, The Sigma Chromatic Number of the Circulant Graphs $$C_n(1,2)$$ , $$C_n(1,3)$$ , and $$C_{2n}(1,n)$$, Chromatic numbers of Cayley graphs of abelian groups: a matrix method, A comparison of lower bounds for the symmetric circulant traveling salesman problem, Circular automata synchronize with high probability, Biclique-colouring verification complexity and biclique-colouring power graphs, Unnamed Item, On Motzkin's problem in the circle group, Hardness of computing clique number and chromatic number for Cayley graphs, Distance graphs with maximum chromatic number, Vertex-colouring of 3-chromatic circulant graphs, Computing the \(k\)-resilience of a synchronized multi-robot system, Layout of random circulant graphs, Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, The Travelling Salesman Problem in symmetric circulant matrices with two stripes, On the independence ratio of distance graphs, Colouring clique-hypergraphs of circulant graphs, Colouring clique-hypergraphs of circulant graphs, On the chromatic number of circulant graphs, Minimum chromaticity of circulant graphs, Block circulant graphs and the graphs of critical pairs of crowns

Cites Work

• Unnamed Item
• Unnamed Item
• Spectral bounds for the clique and independence numbers of graphs
• Permanental compounds and permanents of (0,1)-circulants
• Theorems in the additive theory of numbers
• On fast multiplication of polynomials over arbitrary algebras
• A spectral technique for coloring random 3-colorable graphs (preliminary version)
• Graph Coloring Using Eigenvalue Decomposition
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• An Optimal Circulant Preconditioner for Toeplitz Systems
• On Computing the Discrete Fourier Transform
• On the hardness of approximating minimization problems
• Point-symmetric graphs with a prime number of points
• A new 5‐arc‐transitive cubic graph