Generalised Paley graphs with a product structure

DOI10.1007/S00026-019-00423-0MaRDI QIDQ2421318zbMATH OpenOpenAlexWikidataFDO

Authors Geoffrey Pearce, Cheryl E. Praeger

Publication date 14 June 2019

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06609

zbMATH Keywords

graph automorphismsCartesian products of graphsgeneralised Paley graphs

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A graph is Cartesian decomposable if it is isomorphic to a Cartesian product of (more than one) strictly smaller graphs, each of which has more than one vertex and admits no such decomposition. These smaller graphs are called the Cartesian-prime factors of the Cartesian decomposition, and were shown, by Sabidussi and Vizing independently, to be uniquely determined up to isomorphism. We characterise by their parameters those generalised Paley graphs which are Cartesian decomposable, and we prove that for such graphs, the Cartesian-prime factors are themselves smaller generalised Paley graphs. This generalises a result of Lim and the second author which deals with the case where all the Cartesian-prime factors are complete graphs. These results contribute to the determination, by parameters, of generalised Paley graphs with automorphism groups larger than the 1-dimensional affine subgroups used to define them.

Recommendations

• On generalised Paley graphs and their automorphism groups
• Factoring cartesian‐product graphs
• scientific article; zbMATH DE number 568809
• On subgraphs of Cartesian product graphs
• Unique prime Cartesian factorization of graphs over finite fields

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 1744091 (Why is no real title available?)
• scientific article; zbMATH DE number 2170433 (Why is no real title available?)
• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• scientific article; zbMATH DE number 2230760 (Why is no real title available?)
• A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\)
• Cliques and colorings in generalized Paley graphs and an approach to synchronization
• Codes from incidence matrices and line graphs of Paley graphs
• Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields
• Dessins d'enfants on Riemann surfaces
• Graph multiplication
• Handbook of product graphs
• Lower bounds of Ramsey numbers based on cubic residues
• On Orthogonal Matrices
• On generalised Paley graphs and their automorphism groups
• On the adjacency properties of generalized Paley graphs
• Paley and the Paley Graphs
• Permutation decoding of codes from generalized Paley graphs
• Structure and uniqueness of the \((81,20,1,6)\) strongly regular graph

Cited in

(7)

• Waring numbers over finite commutative local rings
• Graph product structure for non-minor-closed classes
• Generalized Paley graphs equienergetic with their complements
• The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs
• A reduction formula for Waring numbers through generalized Paley graphs
• Paley and the Paley Graphs
• On generalised Paley graphs and their automorphism groups

This page was built for publication: Generalised Paley graphs with a product structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2421318)