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.


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.