Let $G$ be a symmetric $n$-regular graph. For which $k$ it is possible to delete some vertices from $G$ to obtain $k$-regular graph $G'$? For example, if $G$ is icosahedral graph (i.e. $5$-regular graph), then it is possible to obtain $4$-regular, $3$-regular and $2$-regular graphs. But if $G$ is octahedral graph (i.e. $4$-regular graph), then it is impossible to obtain $3$-regular graph. I'm interested in a concrete case, when $G$ is an adjacent graph of faces of $120$-cell (i.e. it is $12$-regular graph with $120$ vertices). How to verify it?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ The edge set of any $2d$-regular graph is a disjoint union of $d$ edge sets of induced 2-regular graphs, thus for all even numbers this holds automatically $\endgroup$– Fedor PetrovCommented Jun 27, 2022 at 20:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Your concrete case is called the 600-cell graph: https://mathworld.wolfram.com/600-Cell.html
For each $k$, you can solve the problem via integer linear programming as follows. Let $G=(N,E)$. For $i\in N$, let binary decision variable $x_i$ indicate whether node $i$ appears. For $(i,j)\in E$, let binary decision variable $y_{ij}$ indicate whether edge $(i,j)$ appears. The constraints are: \begin{align} \sum_{(i,j)\in E: u \in \{i,j\}} y_{ij} &= k x_u &&\text{for $u\in N$} \tag1\label1 \\ x_i + x_j - 1 &\le y_{ij} &&\text{for $(i,j)\in E$} \tag2\label2 \\ \sum_{i\in N} x_i &\ge k+1 \tag3\label3 \end{align}
Constraint \eqref{1} enforces $k$-regularity. Constraint \eqref{2} forces edge $(i,j)$ to appear if nodes $i$ and $j$ appear. Constraint \eqref{3} requires at least $k+1$ nodes.
For $k\in\{1,\dots,12\}$, the problem turns out to be feasible except for $k=11$. Here is one feasible set of deleted nodes for each such $k$: \begin{matrix} k & \text{deleted nodes} \\ \hline 1 & \{3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45, 46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89, 90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120\} \\ 2 & \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44, 45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88, 89,90,91,92,93,95,97,98,99,100,101,102,103,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120\} \\ 3 & \{3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45, 46,47,48,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,82,83,84,85,86,87,88,89,90,91, 92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120\} \\ 4 & \{3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46, 47,48,49,50,51,52,53,54,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,77,78,82,83,84,85,86,87,88,89,90,91,92,93,94,95, 96,98,99,100,101,102,103,104,105,106,107,108,110,111,112,113,114,115,116,117,118,119,120\} \\ 5 & \{3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,23,24,27,28,29,30,31,32,33,34,35,36,39,40,41,42,43,44,45,46,47,48,50,51,52, 53,54,56,57,58,59,60,62,63,64,65,66,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99, 100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120\} \\ 6 & \{3,4,5,7,9,10,11,12,14,15,16,17,18,19,22,23,24,25,26,27,29,30,31,32,33,34,35,36,37,38,42,44,45,46,47,48,50,53,55,56,57,58,59 ,60,61,62,64,67,69,70,71,72,73,74,75,77,78,79,80,82,83,84,85,86,87,88,90,91,92,93,94,95,97,98,99,102,103,104,107,108,109,110,111,112 ,113,114,115,116,117,118\} \\ 7 & \{4,7,14,20,21,24,26,27,30,31,39,41,55,56,60,71,73,76,80,86,88,91,93,96,97,98,99,100,101,103,105,106,107,108,109,111,113,115, 116,117,118,120\} \\ 8 & \{4,7,10,14,19,21,28,29,31,32,33,34,36,37,42,47,50,52,53,56,61,64,65,67,75,76,81,83,89,90,94,96,97,98,100,101,103,104,112,113\} \\ 9 & \{97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120\} \\ 10 & \{8,9,24,25,30,35,41,48,54,55,62,63,73,77,88,92,110,111,114,11\} \\ 12 & \{\} \end{matrix}
-
$\begingroup$ How did you check it? Using some software? It is interesting that there is only one exception, k=11. $\endgroup$ Commented Jun 24, 2022 at 19:42
-
1$\begingroup$ Yes, I used the MILP solver in SAS. The LP relaxation turns out to be feasible. $\endgroup$– RobPrattCommented Jun 24, 2022 at 19:48
-
$\begingroup$ Thanks! Does it provide explicit solutions? $\endgroup$ Commented Jun 24, 2022 at 20:12
-
$\begingroup$ Yes, the solver returns $x$ and $y$ that satisfy the constraints. The $i\in N$ with $x_i=0$ are the nodes to remove. $\endgroup$– RobPrattCommented Jun 24, 2022 at 20:35
-
$\begingroup$ Could you provide these solutions, please? $\endgroup$ Commented Jun 27, 2022 at 15:46