Theorem: Let \(G\) be a simple graph with diameter two and no 4-circuit. Then one of the following is true: (a) The maximum degree is \(n-1\); (b) \(G\) is a Moore graph (i.e. a regular simple graph with diameter 2 and girth 5); (c) \(G\) is a polarity graph (i.e.\ a graph \(G=(V,E)\) associated with a polarity of a projective plane---\(V\) is the point-set of the plane; \(pq\in E\) iff \(p\neq q\) and \(p\) lies on the polar line of \(q\)). Author Bondy acknowledges that their result, which dates back to 1979, was ``subsumed by a theorem of W. M. Kantor [Moore geometries and rank \(3\) groups having \(\mu=1\). Q. J. Math. Oxf., II. Ser. 28, No. 111, 309-328 (1977; Zbl 0406.05020)], but states that ``In the intervening years it has become apparent that this particular case of Kantor's theorem, with its attractive statement and simple proof, is not as widely known as perhaps it merits. For this reason Erdős proposed to me that we resubmit the article for publication.
- Some further results on the eccentric distance sum
- On reverse degree distance
- On the superconnectivity in graphs with odd girth \(g\) and even girth \(h\)
- scientific article; zbMATH DE number 165093 (Why is no real title available?)
- Uniformly dissociated graphs
- scientific article; zbMATH DE number 871174 (Why is no real title available?)
- On the \(\lambda ^{\prime}\)-optimality in graphs with odd girth \(g\) and even girth \(h\)
- scientific article; zbMATH DE number 7720720 (Why is no real title available?)
- Superconnectivity of graphs with odd girth \(g\) and even girth \(h\)
- Matching cutsets in graphs of diameter 2
- Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
This page was built for publication: Graphs of diameter two with no 4-circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1301629)
