All graph considered here are finite, simple and undirected.
We know that a graph $G$ is $k$-edge connected if and only if its line graph is $k$-connected (where $k\in\mathbb{N}$). In particular, if $G$ is $k$-connected, then so is the line graph of $G$.

Let $G$ be a cubic graph. We know that the line graph of $G$ is 4-regular. If the line graph of $G$ is 3-connected, then $G$ is 3-connected as well. Suppose that the line graph of $G$ is 4-connected. Does that mean anything to $G$ more than just "$G$ is 3-connected"? (perhaps, something similar to high cyclic edge-connectivity?).



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.