Abstract | ||
---|---|---|
Let e be a positive integer, p be an odd prime, q=pe, and Fq be the finite field of q elements. Let f,g∈Fq[X,Y]. The graph Gq(f,g) is a bipartite graph with vertex partitions P=Fq3 and L=Fq3, and edges defined as follows: a vertex (p)=(p1,p2,p3)∈P is adjacent to a vertex [l]=[l1,l2,l3]∈L if and only if p2+l2=f(p1,l1) and p3+l3=g(p1,l1). If f=XY and g=XY2, the graph Gq(XY,XY2) contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs Gq(f,g) containing no cycles of length less than eight and not isomorphic to the graph Gq(XY,XY2), even without requiring them to be edge-transitive. So far, no such graphs Gq(f,g) have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.ffa.2016.09.001 | Finite Fields and Their Applications |
Keywords | Field | DocType |
05C35,11T06,11T55,51E12 | Odd graph,Discrete mathematics,Combinatorics,Vertex-transitive graph,Graph power,Bipartite graph,Neighbourhood (graph theory),Degree (graph theory),Extremal graph theory,Universal graph,Mathematics | Journal |
Volume | ISSN | Citations |
43 | 1071-5797 | 3 |
PageRank | References | Authors |
0.53 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xiang-dong Hou | 1 | 296 | 43.20 |
Stephen D. Lappano | 2 | 11 | 2.10 |
Felix Lazebnik | 3 | 353 | 49.26 |