2
$\begingroup$

Suppose $H_1$ and $H_2$ are connected, vertex-transitive graphs, $H_1$ is not the complete graph, and $|V(H_2)| \ge 2$. Then, the lexigraphic product $G=H_1 \circ H_2$ is vertex-transitive, $0 < \kappa(G) < \delta(G)$, and the atomic parts of $G$ are all isomorphic to $H_2$. This remark is mentioned in (Watkins, "Connectivity of Transitive Graphs", JCT 1970, p. 28).

My question is on the last part of the remark on the atomic parts of $G$. I can prove that the atomic parts of $G$ are all isomorphic to $H_2$ under the additional assumption that $\kappa(H_1) = \delta(H_1)$ (and it seems to me this condition is also necessary), as follows. By definition of the lexicographic product, $G$ can be constructed by taking $|V(H_1)|$ copies of $H_2$, and each vertex in the $i$th copy of $H_2$ is joined to each vertex in the $jth$ copy of $H_2$ iff $ij$ is an edge of $H_1$. Thus, any minimum cutset $C$ of $G$ is the vertex set of one or more copies of $H_2$, in fact, of $\kappa(H_1)$ copies of $H_2$. Removing $C$ from $G$ disconnects $G$ into parts, each of which consist of copies of $H_2$. There exists a part which is a single copy of $H_2$ iff $H_1$ has a part consisting of a single vertex, i.e. iff $\kappa(H_1) = \delta(H_1)$.

Is there a way to prove (without using the additional assumption $\kappa(H_1) = \delta(H_1)$) that an atomic part of $G$ is a single copy of $H_2$?

Let me recall the terminology and notation from the paper. The vertex-connectivity and minimal degree of a graph $G$ are denoted $\kappa(G)$ and $\delta(G)$, respectively. The lexicographic product $H_1 \circ H_2$ is defined to be the graph with vertex set $V(H_1) \times V(H_2)$, and two vertices $(x_1,x_2)$ and $(y_1,y_2)$ are adjacent in this graph whenever either ($x_1 y_1$ is an edge in $H_1$) or ($x_1=y_1$ and $x_2 y_2$ is an edge in $H_2$). A part of $G$ is a connected component of $G-C$ for some minimum cutset $C$. An atomic part is a part of smallest order.

$\endgroup$

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.