The characterization of maximum complete and empty subgraphs in the quadrance graph
The characterization of maximum complete and empty subgraphs in the quadrance graph
Let be the finite field with elements, and let be the graph on whose adjacency is determined by the quadrance relation used in the paper. For a subset , say that spans a complete subgraph or an empty subgraph according as every pair of vertices in is adjacent or no pair is adjacent.
Maximum subgraph conjecture. If spans a complete subgraph or an empty subgraph of order in , then is a line in .
The preceding bound shows that a complete or empty subgraph of this type has at most vertices, and equality is attained by the points on a line. Computations for and support the conjectured converse.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Le Anh Vinh, “Quadrance polygons, association schemes and strongly regular graphs”, arXiv:math/0509598 (2005).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.