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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
5
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.
answered Jan 9 '16 at 17:56
-
$\begingroup$ Unfortunately with 3-edge-connectedness Lemma 1 proof is wrong. $\endgroup$ – KKS Jan 14 '16 at 13:13
-
$\begingroup$ You can find an alternative proof here: homepages.math.uic.edu/~mubayi/591/Spring2010/hw3sol.pdf. $\endgroup$ – Yuval Filmus Jan 14 '16 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 '16 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 '16 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 '16 at 15:38
