2
$\begingroup$

Are line graphs of powers of cycles again a power of cycle? I think yes, this is because the line graphs of cycles are cycles of the same order, and moreover, since powers of cycles consist of edge disjoint cycles which are packed within a distance given by the value of the power, their line graphs also must be powers of cycles. Am I right?

The definition of power is use this one. Thanks beforehand.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Have you tried a formal approach, i.e. writing down a formal definition of some cycle power and its line graph? $\endgroup$
    – Watercrystal
    Commented Oct 23, 2020 at 18:14
  • $\begingroup$ I don't think your claim can be true. Try to find a counter-example. Hint: consider the second power of some cycle $C_k$ for some fixed $k$. Can its line graph also be a line graph of a cycle? $\endgroup$
    – Discrete lizard ♦
    Commented Oct 24, 2020 at 11:05
  • $\begingroup$ @DiscreteLizard my claim is that the line graph of a power cycle is some other power of a cycle. In your example, my claim is that the line graph of the square of $C_k$ is isomorphic to the cube of $C_{2k}$. $\endgroup$
    – vidyarthi
    Commented Oct 24, 2020 at 19:14
  • 1
    $\begingroup$ @vidyarthi Ok. I think the claim in your question may be true. But the square of the line graph of $C_k$ would only be isomorphic to a power of $C_{\min \{2k, k(k-1)/2 \}}$. $\endgroup$
    – Discrete lizard ♦
    Commented Oct 24, 2020 at 20:56

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.