4
$\begingroup$

Find the samllest number of edges in 6-vertex-connected graph on 200 vertices.

I think that the answer is 600 , using the fact that $\delta(G) \geq \kappa(G)$.

But the smallest 6-vertex-connected graph that I could come up with is $K_{6,194}$ (the complete bipartite graph with size 6 and 194) , which sounds like far from optimal...

A hint/intuition will be very helpful .

$\endgroup$
  • 1
    $\begingroup$ I would think that the graph with adjacencies defined as $v_i$ is adjacent to $v_{j}$ with $j=((-1+i+n)\text{mod} 200)+1$, $n\in\{-3,-2,-1,1,2,3\}$. (I.e. $v_4$ is adjacent to each of $v_1,v_2,v_3,v_5,v_6,v_7$ whereas $v_1$ is adjacent to $v_{198},v_{199},v_{200},v_2,v_3,v_4$). Each vertex has exactly 6 edges, and you can check that it is in fact six-connected. $\endgroup$ – JMoravitz Jul 14 '15 at 17:25
  • $\begingroup$ As Rebecca has deleted her answer, based on your comment there I've edited in the info about vertex connectivity, please roll back the edit if this is against your intention. $\endgroup$ – dtldarek Jul 14 '15 at 17:40
  • $\begingroup$ @JMoravitz I thoguht about something almost identical (to connect each vertex to the next 6 vertices) , but it failed .Your example is excellent!! $\endgroup$ – UserB95 Jul 14 '15 at 18:25
  • 2
    $\begingroup$ Here's another example: Let $G_i$ be a graph isomorphic to $K_5$ with $V(G_i) = \{v_i^1, v_i^2, v_i^3, v_i^4, v_i^5\}$, for $i = 1,2,\dots,40$. Now let $G$ be the union of all the $G_i$'s together with all edges $v_i^j v_{i+1}^j$ for $i=1,2,\dots,40$, and $j=1,2,\dots,5$, where subscripts are taken mod 40. There are 400 vertices, and you can check that it is 6-connected and 6-regular. $\endgroup$ – Perry Elliott-Iverson Jul 14 '15 at 20:01
  • $\begingroup$ Note that JMoravit'z example is in fact, the answer, since in any $k$-vertex connected graph, all vertices must have degree at least $k$. $\endgroup$ – Irvan Jul 15 '15 at 9:50
0
$\begingroup$

As JMoritz noted :

I would think that the graph with adjacencies defined as $v_i$ is adjacent to $v_j$ with $j=((−1+i+n) \ mod \ 200)+1,$ $n∈\{−3,−2,−1,1,2,3\}$. (I.e. $v_4$ is adjacent to each of $v_1,v_2,v_3,v_5,v_6,v_7$ whereas $v_1$ is adjacent to $v_{198},v_{199},v_{200},v_2,v_3,v_4$). Each vertex has exactly 6 edges, and you can check that it is in fact six-connected(the easiest way is to see that thee are 6 vertex disjoint paths between every two vertices, then by Menger's we could conclude that the graph is 6 connected)

$\endgroup$

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.