22
$\begingroup$

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.

$\endgroup$
3

4 Answers 4

20
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer. This is exactly what I was looking for. I will accept it later to leave the question open for others. $\endgroup$
    – Rebel Yell
    Jul 6, 2023 at 21:47
  • 5
    $\begingroup$ This question is really part of a huge swathe of questions (including Conway's 99 graph problem) about existence of strongly regular graphs with certain parameters. $\endgroup$ Jul 7, 2023 at 10:34
  • 8
    $\begingroup$ @RebelYell For this type of question, I think it is acceptable etiquette to not accept a single answer. $\endgroup$ Jul 7, 2023 at 12:05
  • 1
    $\begingroup$ @TimothyChow thanks, was hesitating about it, think this would be more correct. $\endgroup$
    – Rebel Yell
    Jul 7, 2023 at 13:22
  • $\begingroup$ @SeanEberhard this is a valuable remark. I have this list of known and unknown strongly regular graphs (actually, I've been proving Conway's 99 graph problem for more than a year): win.tue.nl/~aeb/graphs/srg/srgtab.html. Yet, I don't know which unknown cases are especially interesting if we can make such selection at all. $\endgroup$
    – Rebel Yell
    Jul 7, 2023 at 13:30
16
$\begingroup$

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.)

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Surely you don't mean to say that the number of Hamiltonian paths in a complete graph is an open question? $\endgroup$ Jul 8, 2023 at 21:47
  • $\begingroup$ @GerryMyerson Thanks for pointing that out, I'm not very familiar with the area. I corrected the statement. If you have a better description on what is or isn't known feel free to edit. $\endgroup$
    – quarague
    Jul 9, 2023 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.