2
$\begingroup$

What is the definition for k-line-connectedness of the graph ? I am in doubt whether it differs from usual k-vertex (edge) connectedness. I've encountered it in the paper titled "Np-complete problems on a 3-connected cubic planar graph and their applications" where it comes without definition. Unfortunately for me I couldn't get the definition from the context given in its authors' proofs.

$\endgroup$

1 Answer 1

3
$\begingroup$

Judging from the proof of Lemma 1 in the paper, 3-line-connected is the same as 3-edge-connected; line is probably a translation from Japanese.

$\endgroup$
5
  • $\begingroup$ Unfortunately with 3-edge-connectedness Lemma 1 proof is wrong. $\endgroup$
    – KKS
    Jan 14, 2016 at 13:13
  • $\begingroup$ You can find an alternative proof here: homepages.math.uic.edu/~mubayi/591/Spring2010/hw3sol.pdf. $\endgroup$ Jan 14, 2016 at 13:19
  • $\begingroup$ This is OK now. Thanks. Let me wait a bit to get final check for this answer. :-) $\endgroup$
    – KKS
    Jan 14, 2016 at 14:19
  • $\begingroup$ After the second reading I get that this Japanese paper contains wrong proofs. That's sad. Not only for 3-connectedness = 3-edge-connectedness statement but also for main results. $\endgroup$
    – KKS
    Jan 14, 2016 at 16:35
  • $\begingroup$ For example, for completeness of VC when replacing the 1-disconnecting edges the situation could happen when the gadget is adjacent to at least two gadgets. In this case obtained graph is not cubic, $\endgroup$
    – KKS
    Jan 15, 2016 at 15:38

Your Answer

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

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