Is there any result or known way to find complete minors of graphs? I want to find complete minors of generalized Petersen graphs and $3$-regular graphs. I guess that generalized Petersen graphs $G (n, k)$ for $n > 5$ are $K_5$-minor-free but I'm not sure and I can't prove that. Can you guide me?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Not sure about general results for finding minors, but the generalised Petersen graph $G(k^2,k)$ has a $K_k$ minor.
Denote the vertices of $G(k^2,k)$ by $v_0,\dots, v_{k^2-1}, w_0, \dots w_{k^2-1}$ with edges from $v_{i}v_{i+1}$, $w_{i}w_{i+k}$, and $v_iw_i$ (where addition of indices is modulo $k^2$).
For $0 \leq s < k$, let $V_s := \{v_{ks+j} \mid 0 \leq j < k \}$ and let $W_s = \{w_{s+kj}\mid 0 \leq j < k\}$. This clearly defines a partition of the vertex set. Each $V_s$ and each $W_s$ induces a connected graph because $v_{i}v_{i+1}$ and $w_{i}w_{i+k}$ are edges. Moreover, each $V_s$ is connected to every $W_t$ by the edge $v_{ks+t}w_{t+ks}$.
Hence, taking the branch sets $X_s = V_s \cup W_s$ gives a $K_k$ minor.
