0
$\begingroup$

An outerplanar graph is an undirected graph that can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges. Alternatively, a graph G is outerplanar if the graph formed from G by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph.

The join $G=G_1+G_2$ of graphs $G_1$ and $G_2$ with disjoint point sets $V_1$ and $V_2$ and edge sets $X_1$ and $X_2$ is the graph union $G_1$ union $G_2$ together with all the edges joining $V_1$ and $V_2$.

Does it exist An outerplanar $G$ graph such that $G+ k_1$ is not planar graph? where $k_1$ is a vertex. can you help me?

$\endgroup$
  • 3
    $\begingroup$ What is definition of $k1$? $\endgroup$ – coffeemath Nov 22 '18 at 8:08
  • 1
    $\begingroup$ Isn't $G+k_1$ planar when $G$ is outerplanar, precisely because of the sentence "Alternatively, a graph G is outerplanar if the graph formed from G by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph."? $\endgroup$ – Servaes Nov 22 '18 at 11:48
  • $\begingroup$ I agree with that, iff $k_1$ is really supposed to mean the regular graph on one vertex (aka graph with a single vertex and no edges) $\endgroup$ – Ingix Nov 22 '18 at 12:10
  • $\begingroup$ A graph is outerplanar if and only if it does not contain $K_4$ or $K_{2,3}$ as minor. $\endgroup$ – mathpadawan Nov 24 '18 at 11:15

Your Answer

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

Browse other questions tagged or ask your own question.