Brute force open problems in graph theory

Question

Usually, a graph theoretic problem asks whether some class of graphs $C$ possesses a quality $P$. For example, $C$ is the class of all graphs and $P$ is the reconstructability property in Kelly-Ulam conjecture. Also, $C$ is the class of trees and $P$ is the existence of some graceful labeling in the graceful tree conjecture. The formal definition of a proof (the Hilbert-style deduction system) implies any provable assertion can be, in principle, proved by a computer. Yet in our examples, it's far from obvious how the program executed by a computer must look like to give us the proof in some period of time.

Meanwhile, there is another type of graph theoretic problems where the idea of the computer proof is straightforward. Namely, when we ask whether some $n$-vertex graph possesses a property $P$. Then we can simply use brute force generating $2^{n(n-1)/2}$ possible graphs with the vertex set $\{1,...,n\}$ and checking whether all graphs satisfy $P$. An example here is Conway's 99-graph problem asking about the existence of a $99$-vertex graph in which all pairs of adjacent and non-adjacent vertices have exactly $1$ and $2$ common neighbors, respectively. Denoting this last property as $Q$ and proving there is no such graph, we may put $n=99$ and $P=\neg Q$. Another example concerns diagonal Ramsey numbers. Say, the value of $R(5,5)$ is still unknown and we just have $43\leq R(5,5)\leq48$. If we want to improve these bounds proving $R(5,5)\leq47$, it's sufficient to generate all $2^{1081}$ $2$-edge-colorings of $K_{47}$ and check that they contain $K_5$ of one color. Here, $n=47$ and $P$ can be stated as a graph or its complement contain $K_5$.

I think that problems of the second type are of some philosophical interest. Namely, they are quite simple for understanding (at least we know how a computer could prove them) and still difficult to find the solution within a reasonable period. My question is about some other graph theoretic problems of this type you are familiar with.

Answer 1

The existence of a 57-regular "Moore graph" is one such problem.

We define the diameter of a graph $G$ to be the least $l$ such that any two vertices $u,v$ have a path between them using $\le l$ edges. We define the girth of $G$ to be the least $g$ such that there is a cycles $C\subset G$ with $g$ edges. Assuming $G$ has minimum degree $2$, it is not hard to show that $\textrm{girth}(G)\le 2\textrm{diameter}(G)+1$.

Moore graphs are $d$-regular graphs $G$ satisfying $\textrm{girth}(G) = 2\textrm{diameter}(G)+1 $ (which is best possible). This is a very strong assumption, and you can prove lots of things about what potential Moore graphs must look like.

The finitary question is: does there exist a 3250-vertex graph $G$, where each vertex has degree $57$, with girth $5$ and diameter $2$. An answer to this would tell us exactly which $d$ can there exist $d$-regular Moore graphs.

Answer 2

Elaborating on the comment of Wojowu, for what positive integers $q$ does there exist a bipartite graph $G$ with vertex bipartition $(A,B)$ satisfying: (a) $|A|=|B|=q^2+q+1$, (b) $G$ is regular of degree $q+1$, (c) any two vertices in $A$ are adjacent to a unique vertex in $B$, and (d) any two vertices in $B$ are adjacent to a unique vertex in $A$? This is equivalent to the existence of a projective plane of order $q$. The smallest open case is $q=12$. (Condition (a) is superfluous.)

Answer 3

Question: Does $K_{50}$ decompose into seven copies of the Hoffman-Singleton graph?

The following is copied from https://faculty.math.illinois.edu/~west/openp/hoffsing.html

Definitions: The Hoffman-Singleton graph [HS] is a $7$-regular graph with girth $5$ on $50$ vertices. It is the only such graph with the fewest vertices, which makes it the unique $(7,5)$-cage. (Other proofs of uniqueness appear in [FS, OW].) The graph consists of ten $5$-cycles $P_0,\dotsc,P_4$ and $Q_0,\dotsc,Q_4$, each with vertices modulo $5$, and vertex $i$ of $P_j$ adjacent to vertex $i+jk \mod 5$ of $Q_k$.

Question: Does $K_{50}$ decompose into $7$ copies of the Hoffman-Singleton graph?

Comments/Partial results: Meszka and Siagiova [MS] have found five edge-disjoint copies of the Hoffman-Singleton graph in $K_{50}$, using voltage graph methods.

References:
[FS] Fan, C.; Schwenk, A. J. Structure of the Hoffman-Singleton graph. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr. Numer. 94 (1993), 3--8.
[HS] Hoffman, A. J.; Singleton, R. R. On Moore graphs with diameters 2 and 3. IBM J. Res. Develop. 4 1960 497--504.
[MS] Meszka, M.; Siagiova, J. A covering construction for packing disjoint copies of the Hoffman-Singleton graph into $K_{50}$. J. Combinatorial Designs, to appear.
[OW] O'Keefe, M.; Wong, P. K. On certain regular graphs of girth 5. Internat. J. Math. Math. Sci. 7 (1984), no. 4, 785--791.

Answer 4

There was a question on the math stack exchange a few days ago which essentially asks:

Given a number of edges and vertices, which graph has the maximal number of Hamiltonian paths and how many are there?

For any given numbers of edges and vertices there are only finitely many graphs so this is a straight forward brute force computation. For a number of special cases the number of Hamiltonian paths is known but afaik the general case is still open.