ARTICLE
TITLE

The EKR-Module Property of Pseudo-Paley Graphs of Square Order

SUMMARY

We prove that a family of pseudo-Paley graphs of square order obtained from unions of cyclotomic classes satisfies the Erdos-Ko-Rado (EKR) module property, in a sense that the characteristic vector of each maximum clique is a linear combination of characteristic vectors of canonical cliques. This extends the EKR-module property of Paley graphs of square order and solves a problem proposed by Godsil and Meagher. Different from previous works, which heavily rely on tools from number theory, our approach is purely combinatorial in nature. The main strategy is to view these graphs as block graphs of orthogonal arrays, which is of independent interest.

PAGES
pp. P4.33

 Articles related

Grahame Erskine, James Tuite    

The search for the smallest possible dd-regular graph of girth gg has a long history, and is usually known as the cage problem. This problem has a natural extension to hypergraphs, where we may ask for the smallest number of vertices in a dd-regular, rr-... see more


Baptiste Louf, Fiona Skerman    

In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by Krivelevich [SIAM J. Disc. Math. 32 1 (2018)]. Here, we show that the problem... see more


Dror Chawin, Ishay Haviv    

A graph GG is said to be kk-subspace choosable over a field FF if for every assignment of kk-dimensional subspaces of some finite-dimensional vector space over FF to the vertices of GG, it is possible to choose for each vertex a nonzero vector from its s... see more


Jialu Zhu, Xuding Zhu    

  For a graph GG and a positive integer nn, the nnth cone over GG is obtained from the direct product G×PnG \times P_n of GG and a path Pn=(0,1,…,n)P_n=(0,1,\ldots, n), by adding a copy of GG on V(G)×{0}V(G) \times \{0\}, and identifying V(G)×{n}V(G... see more


Arnbjörg Soffía Árnadóttir, Waltraud Lederle, Rögnvaldur G. Möller    

We study groups acting vertex-transitively and non-discretely on connected, cubic graphs (regular graphs of degree 3). Using ideas from Tutte's fundamental papers in 1947 and 1959, it is shown that if the action is edge-transitive, then the graph has to ... see more