Cyclic and cliquewise connectedness of line graphs
Motivated by former investigations about connections between the connectivity number of a graph \(G\) and the edge-connectivity number of its line graph \(L(G)\), the author looked for similar connections between cyclic connectivity and cyclic edge-connectivity and between cliquewise connectivity and cliquewise edge-connectivity: The cyclic connectivity number \(\kappa_c(G)\) of a graph \(G\) is the smallest number of vertices whose deletion decomposes \(G\) into components such that at least two of them contain a cycle. If no such vertices exist, then \(\kappa_c(G)\) is infinite. The cyclic edge-connectivity number \(\lambda_c(G)\) of \(G\) is defined analogously (replace ``vertices'' by ``edges''). Finally, by considering maximal complete subgraphs of \(G\) with at least three vertices instead of cycles, the cliquewise connectivity number \(\kappa_{cw}(G)\) and the cliquewise edge-connectivity number \(\lambda_{cw}(G)\) of \(G\) are defined. The author proves that \(\lambda_c(G)= \kappa_c(L(G))\) if \(2\leq\lambda_c(G)<\infty\) and the minimal degree of \(G\) is large enough. Moreover, she shows that \(\lambda_c(G)= \kappa_{cw}(L(G))\) if \(\kappa_{cw}(L(G))<\infty\) and if, again, \(2\leq\lambda_c(G)<\infty\) and the minimal degree of \(G\) is large enough.
scientific article; zbMATH DE number 1047070