Cyclic and cliquewise connectedness of line graphs
type: Item
instance of: scholarly article
title: Cyclic and cliquewise connectedness of line graphs
zbMATH Open document ID: 0881.05078
DOI: 10.1016/S0012-365X(96)00120-3
published in: Discrete Mathematics
publication date: 1998-02-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1047070
zbMATH Keywords: connectivity number
zbMATH Keywords: edge-connectivity number
zbMATH Keywords: line graph
zbMATH Keywords: connectivity
author: Christina Maria Zamfirescu
reviewed by: Andreas Huck
MaRDI profile type: Publication
cites work: The connectivity of line-graphs
cites work: Parallel concepts in graph theory
cites work: On the line-connectivity of line-graphs
full work available at URL: s0012-365x(96)00120-3
OpenAlex ID: W1968968742
description: scientific article; zbMATH DE number 1047070