The _k-connectivity of line graphs

DOI10.1016/J.DAM.2020.05.002MaRDI QIDQ2197398zbMATH OpenOpenAlexFDO

Authors Hengzhe Li, Yuan-Yuan Lu, Baoyindureng Wu, Ankang Wei

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.05.002

\(\kappa_k\)-connectivity \(\lambda_k\)-connectivity line graph wheel

Trees (05C05) Enumeration in graph theory (05C30) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Review text

For a subset \(S\) of the vertex set of a graph \(G\) with \(|S|\geq 2\), let \(\kappa_{G}(S)\) (\(\lambda_{G}(S)\)) denote the maximum number of internally disjoint (edge-disjoint) trees of \(G\) such that each pair of these trees has exactly \(S\) in common. The generalized \(k\)-connectivity (\(k\)-edge-connectivity) of \(G\) is defined as \(\kappa_{k}(G)=\min\{\kappa_{G}(S) \mid S \subseteq V(G) \text{ and } |S|=k\}\) (\(\lambda_{k}(G)=\min\{\lambda_{G}(S)\mid S \subseteq V(G) \text{ and } |S|=k\}\)). Let \(L(G)\) denote the line graph of \(G\). The relation between \(\kappa_{k}(L(G))\) and \(\lambda_{k}(G)\) is investigated and it is shown that \[\kappa_{k}(L(G))\geq \lambda_{k}(G)-\Bigm\lceil{\frac{\lceil{\frac{\operatorname{mad}(G)}{2}\rceil}}{2}}\Bigm\rceil, \] where \(\operatorname{mad}(G)\) is the maximum average degree of \(G\), \(\kappa_{k}(L(G))\geq \lambda_{k}(G)-\Bigm\lceil{\frac{\lfloor{\frac{r}{2}\rfloor}}{2}}\Bigm\rceil\) for any integers \(k\) and \(r\) with \(k\leq \binom{r}{2}\) and the conjecture \(\kappa_{k}(L(G))\geq \lambda_{k}(G)\) holds for three cases: \(k=5\), \(G\) is the wheel graph and \(G\) is the complete bipartite graph \(K_{3,n}\).

Recommendations

Cites work

Cited in

(11)

This page was built for publication: The \(\kappa_k\)-connectivity of line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197398)