0
$\begingroup$

I am revising my lecture notes about connectivity, but I am stuck regarding proof of $κ(Q_d) = d$ Then I took a look of the proof by induction in D. West's book. For $d\leq1$, $Q_d$ is a clique with $k+1$ vertices and connectivity $k$.Can anyone visualize that statement about $k+1$ vertices? Also, it would be great if you have another proof or explanation to articulate my understanding of it. Thanks

$\endgroup$

closed as off-topic by YCor, bof, Chris Godsil, Mark Wildon, Ben Barber Nov 27 '18 at 10:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – bof, Chris Godsil, Mark Wildon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Did you mean "$Q_d$ is a clique with $d+1$ vertices and connectivity $d$? $\endgroup$ – bof Nov 24 '18 at 12:52
  • $\begingroup$ What is hard to visualize about the graphs $Q_0=K_1$ and $Q_1=K_2$? $\endgroup$ – bof Nov 24 '18 at 12:53
1
$\begingroup$

You can connect any two vertices by $d$ vertex-disjoint paths directly. If they differ in $k$ coordinates, $k$ paths will be in the $k$-cube in which they are opposite (use coordinates in the cyclic order). The rest are formed by moving along extra coordinate axis to an adjacent $k$-cube, going to the opposite vertex in it, and moving along the extra axis backwards.

$\endgroup$
0
$\begingroup$

We can define the Hypercube $Q_{k}$ recursively, as follows. We let $Q_{0}=K_{1}$ and $Q_{k}=Q_{k-1}\square K_{2}$, for all $k\geq1$. Let us observe that $Q_{k}$, $k\geq1$, is obtained from two disjoint copies of $Q_{k-1}$ by joining their corresponding vertices.

Now, we prove that $\kappa(Q_{k})=k$. We proceed by induction on $k$. The equality is obvious for $k=0$ and $k=1$. In such cases the Hypercube is isomorphic to $K_{1}$ and $K_{2}$, respectively. Now let we have the equality for all Hypercubes of order less that $k$ and prove the equality for a Hypercube of order $k$. We now consider the Hypercube $Q_{k}$. It is well-known that $\kappa(G)\leq \delta(G)$, for all graphs $G$. Therefore, \begin{equation}\label{Q1} \kappa(Q_{k})\leq \delta(Q_{k})=k. \end{equation} Suppose to the contrary that $\kappa(Q_{k})\leq k-1$. Let $G_{1}$ and $G_{2}$ be those two copies of $Q_{k-1}$ as subgraphs of $Q_{k}$. Let $S$ be a $\kappa(Q_{k})$-set. We consider two cases.

Case 1. $S\subseteq V(G_{1})$ or $S\subseteq V(G_{2})$. By symmetry we may assume that $S\subseteq V(G_{2})$. Since $|S|\leq k-1\leq2^{k-1}$, the graph $G-S$ is obtained from a copy of $Q_{k-1}$ by adding $2^{k-1}-|S|$ new vertices such that every new vertex has exactly one neighbor in $V(Q_{k-1})$ (note that there are some possible edges among the new vertices). So, $G-S$ is connected which is a contradiction..

Case 2. $S\cap V(G_{1})\neq\emptyset$ and $S\cap V(G_{2})\neq\emptyset$. Then, $|S\cap V(G_{1})|<k-1$ and $|S\cap V(G_{2})|<k-1$. Therefore, both $G_{1}'=G_{1}-(S\cap V(G_{1}))$ and $G_{2}'=G_{2}-(S\cap V(G_{2}))$ are connected by the induction hypothesis. On the other hand, there are some edges with one end point in $V(G_{1}')$ and the other in $V(G_{2}')$. This shows that $G-S$ is connected, a contradiction.

Therefore, $\kappa(Q_{k})=k$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.