4
$\begingroup$

I would like to get a $5$-regular graph with diameter $2$ on $22$ vertices.

I know that there are 5-regular graphs with diameter 2 on 20 vertices and also on 24 vertices. The one on 24 vertices can be constructed with the help of twisted or star product ($K_3*X_8$), however as I see such twisted product cannot work on 22 vertices, and there are about $10^{19}$ connected 5-regular graphs on 22 vertices, so generating all of them and selecting those with diameter 2 is hopeless for me. Any ideas how to construct such graph? Or is there any known graphs with these properties?

Edit

Big thanks to Rob Pratt for the solution found by linear programming. The adjacency matrix of a 5-regular graph with diameter 2 is the following:

\begin{matrix} 0& 1& 0& 1& 0& 1& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 1& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 1& 1& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 1& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 0\\ 0& 0& 0& 0& 0& 1& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 0& 0& 1& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 1& 0& 0& 0& 0& 1& 0 \end{matrix} Thank you for the answers!

$\endgroup$
  • $\begingroup$ There is something called "the $(11,5,2)$ incidence graph" that may be an answer to your question. $\endgroup$ – Gerry Myerson Jul 5 at 11:53
  • $\begingroup$ Unfortunately the (11,5,2) incidence graph's diameter is 3, I have just checked it, anyway, thank you for your answer. $\endgroup$ – Sz Zs Jul 5 at 12:27
  • 1
    $\begingroup$ Can you add an explicit description/depiction of a 5-regular graph on 24 vertices with diameter 2? Maybe it is enough to remove two vertices from such graph and glue together the edges with a free endpoint after the vertex removal. $\endgroup$ – Jack D'Aurizio Jul 5 at 17:52
  • $\begingroup$ Well, I thought about that, but I think it is not possible in this case. For example if you remove any edges of that graph (only one) the diameter will become 3, so removing 2 vertices and then trying to connect the free endpoints probably will not work as well. I am trying to copy and paste the adjacency matrix of that graph here, but the comment would be too long. :) I will try to edit the original question. $\endgroup$ – Sz Zs Jul 5 at 18:04
  • $\begingroup$ Still trying to figure out a simple "connection rule". Can you describe what do you mean by $X_8$? I am not familiar with such nomenclature. $\endgroup$ – Jack D'Aurizio Jul 5 at 18:40
4
$\begingroup$

Here's one:

$$(1, 2), (1, 4), (1, 6), (1, 8), (1, 11), (2, 10), (2, 12), (2, 17), (2, 21), (3, 4), (3, 8), (3, 17), (3, 18), (3, 20), (4, 9), (4, 10), (4, 22), (5, 6), (5, 9), (5, 13), (5, 18), (5, 21), (6, 14), (6, 16), (6, 20), (7, 8), (7, 9), (7, 11), (7, 12), (7, 16), (8, 19), (8, 21), (9, 12), (9, 15), (10, 16), (10, 18), (10, 19), (11, 13), (11, 15), (11, 18), (12, 14), (12, 17), (13, 17), (13, 19), (13, 22), (14, 18), (14, 19), (14, 22), (15, 19), (15, 20), (15, 21), (16, 20), (16, 22), (17, 20), (21, 22)$$

I obtained this via integer linear programming as follows. Let $N=\{1,\dots,22\}$ be the nodes, and let $P=\{i\in N, j\in N: i<j\}$ be the set of node pairs. For $(i,j)\in P$, let binary decision variable $x_{i,j}$ indicate whether $(i,j)$ is an edge. For $(i,j)\in P$ and $k \in N \setminus \{i,j\}$, let binary decision variable $y_{i,j,k}$ indicate whether $k$ is a common neighbor of $i$ and $j$. The constraints are: \begin{align} \sum_{(i,j)\in P:\ k \in \{i,j\}} x_{i,j} &= 5 &&\text{for $k\in N$} \tag1\\ x_{i,j} + \sum_{k \in N \setminus \{i,j\}} y_{i,j,k} &\ge 1 &&\text{for $(i,j)\in P$} \tag2\\ y_{i,j,k} &\le [i<k]x_{i,k} + [k<i]x_{k,i} &&\text{for $(i,j)\in P$ and $k \in N \setminus \{i,j\}$} \tag3\\ y_{i,j,k} &\le [j<k]x_{j,k} + [k<j]x_{k,j} &&\text{for $(i,j)\in P$ and $k \in N \setminus \{i,j\}$} \tag4 \end{align} Constraint $(1)$ enforces $5$-regularity. Constraint $(2)$ enforces diameter $2$. Constraints $(3)$ and $(4)$ enforce that $y_{i,j,k}=1$ implies $k$ is a neighbor of $i$ and $j$, respectively.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, this one is perfect. :) I have not thought about integer linear programming, but this is a great idea! I am really grateful and happy now! :) Thank you! $\endgroup$ – Sz Zs Jul 5 at 18:36
  • 1
    $\begingroup$ Glad to help. Why were you interested in these particular values (22, 5, and 2)? $\endgroup$ – RobPratt Jul 5 at 18:47
  • $\begingroup$ We are working on a paper in which we needed such a graph, but I have sent you a detailed e-mail in connection with this, I hope that you will see it. Thank you for everything! $\endgroup$ – Sz Zs Jul 6 at 1:37
1
$\begingroup$

Edit

This construction produce a graph with diameter $3$. I think using more delicate construction a correct graph can be built.

Construction

I think you can use 4 copies of $K_5$ with another 2 vertices denote by $u,v$.

by adding:

  1. $1$ edge between two different $K_5$ ($6$ edges total)
  2. Adding 4 edges from $u$ to any one of the $K_5$.
  3. Same for $v$
  4. Connect $u,v$

I think this could be done without creating a vertex with degree bigger than $5$.
Proving the diameter is exactly 2, should not be too hard.
Simple counting argument proves that if no vertex has degree bigger than $5$, then the graph must be $5$ regular.

I think I have in mind a concrete construction.
Let me know if you are having difficulties filling in the details.

Diameter

I'll prove the diameter is exactly 2 in two parts.

First, let's look at each complete subgraph in $G$ as a vertex.
Denote the new graph by $H$. $H$ has $5$ vertices:

  • 4 for each one of the $K_5$.
  • 1 for $u,v$ that form a $K_2$.

$H$ is a complete graph and therefore has diameter 1.

Secondly, every vertex in $H$ diameter (in G) is exactly 1, as it is a complete graph.

Lastly, every path between two vertices, can be viewed as one edge in $H$ and another one not in $H$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Thank you for your answer! I think I understand the construction method you have mentioned, however I cannot see how the diameter should be 2. The distance of $u$ and $v$ from any other vertices is at most 2, this is clear. However, if I connect the different $K_5$ graphs with only one edge, then there will be many pair of vertices which distance is 3. Or did I misunderstand something? $\endgroup$ – Sz Zs Jul 5 at 16:04
  • $\begingroup$ I'm starting to think this can not be done... $\endgroup$ – TheHolyJoker Jul 5 at 16:34
  • $\begingroup$ Well, I think there should be such a graph, but yeah, it is probably difficult to construct it. The 5-regular graph on 24 vertices with 2 diameter is the largest 5-regular one with diameter 2, and to the best of my knowledge it is not proven, but considered to be unique. So probably there are not too many such graphs, but I am really convinced that there should be one. $\endgroup$ – Sz Zs Jul 5 at 16:50
  • $\begingroup$ BTW can you please clarify what $X_8$ is? I think you called it the twisted star $\endgroup$ – TheHolyJoker Jul 5 at 16:54
  • $\begingroup$ $X_8$ is a 3-regular graph with diameter 2 on 8 vertices. There are two such graphs, one is the Wagner graph and the other one is the $X_8$. I was talking about $K_3*X_8$ where $*$ denotes the twisted product (in other articles it is mentioned as star product), loosely speaking it means that we are looking for triangles between the 3 X8 graphs in a particular way that the diameter will be 2. $\endgroup$ – Sz Zs Jul 5 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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