Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Beginning with the complete graph $K_{n}$ for $n\geq 3$ and construct a new graph $G_{n}$ from it such that $G_{n}$ contains every vertex from the circular graph layout of $K_{n}$.

For instance, if I have $K_{37}$:

And wherever there's a crossing, emplace another vertex, yielding $G_{37}$

  • What properties of $G_{n}$ immediately follow from those of $K_{n}$? It's pretty clear that there's a graph homomorphism $\psi_{n}:K_{n}\rightarrow G_{n}$, and also clear that there are some properties of $K_{n}$ which are lost in $G_{n}$.

  • Which computational graph theory package would be best for coping with $G_{n}$? Given how fast the vertex count of $G_{n}$ increases, I think I'd need something comfortable with graphs of several thousand vertices

share|improve this question
No. I mean that every where there is a crossing in the circular layout of $K_{n}$, we emplace a new vertex, yielding $G_{n}$. In the above picture $K_{37}$'s vertices are the points on the periphery, where $G_{37}$'s vertices are the points on the periphery and the crossings. –  deoxygerbe Jun 25 '13 at 20:03
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.