The minimum size of a graph with given tree connectivity
The paper under review investigates generalizations of connectivity, where a path between two vertices is changed to a tree containing some \(k\) vertices. Given a graph \(G\) a set of vertices \(S\subseteq V(G)\), let \( \kappa_G(S)\) denote the maximum number of trees, which are (1) subgraphs of \(G\), (2) pairwise edge-disjoint, (3) the common vertices of any two of the trees is exactly \(S\). (Such trees are called internally disjoint.) Similarly, let \( \lambda_G(S)\) denote the maximum number of trees, which are (1) subgraphs of \(G\), (2) pairwise edge-disjoint. (Such trees are called edge-disjoint.) Let \(\kappa_k(G)\) and \(\lambda_k(G)\) defined as \(\kappa_k(G) =\min \{ \kappa_G(S) : S\subseteq V(G), |S|=k\}\) and \(\lambda_k(G) =\min \{ \lambda_G(S) : S\subseteq V(G), |S|=k\}\). Let \(f(n, k, t)\) (\(g(n, k, t)\)) be the minimum size of a connected graph \(G\) with order \(n\) and \(\kappa_k(G) = t\) (\(\lambda_k(G) = t\)), where \(3 \leq k \leq n\) and \(1 \leq t \leq n-\lceil k/2\rceil\). When \(t\) is arbitrary, the paper obtains upper bounds of both \(f(n, k, t)\) and \(g(n, k, t)\) for \(k =3, 4, 5\), and shows that these bounds can be attained. When \(k\) is arbitrary, the paper obtains an upper bound of \(g(n, k, t)\) for \(t =1, 2, 3, 4\) and an upper bound of \(f(n, k, t)\) for \(t =1, 2, 3\). These bounds can also be attained.
- The minimal size of a graph with generalized connectivity _3=2
- Note on the generalized connectivity.
- The minimal size of a graph with given generalized 3-edge-connectivity.
- On the maximum and minimum sizes of a graph with given \(k\)-connectivity
- On minimally 2-connected graphs with generalized connectivity \(\kappa_3=2\)
- A sharp lower bound for the generalized 3-edge-connectivity of strong product graphs
- A solution to a conjecture on the generalized connectivity of graphs
- Edge-Disjoint Spanning Trees of Finite Graphs
- Generalized 3-edge-connectivity of Cartesian product graphs.
- Generalized Connectivity of Graphs
- Graph theory
- Graphs with large generalized (edge-)connectivity
- scientific article; zbMATH DE number 2209521 (Why is no real title available?)
- Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
- Note on the generalized connectivity.
- Note on the spanning-tree packing number of lexicographic product graphs
- On the difference of two generalized connectivities of a graph
- On the generalized (edge-)connectivity of graphs
- On the Problem of Decomposing a Graph into n Connected Factors
- On the spanning tree packing number of a graph: A survey
- Packing Steiner trees: A cutting plane algorithm and computational results
- Pendant tree-connectivity
- Rainbow trees in graphs and generalized connectivity
- Sharp upper bounds for generalized edge-connectivity of product graphs
- Spanning trees: A survey
- Steiner minimal trees
- Steiner tree problems in computer communication networks.
- The generalized 3-connectivity of Cartesian product
- The generalized 3-connectivity of lexicographic product graphs
- The minimal size of a graph with given generalized 3-edge-connectivity.
- The Steiner tree packing problem in VLSI design
- Tree connectivities of Cayley graphs on abelian groups with small degrees
- Minimum degree and minimum number of edge-disjoint trees
- \(k\)-tree connectivity of line graphs
- On the maximum and minimum sizes of a graph with given \(k\)-connectivity
- The minimal size of a graph with given generalized 3-edge-connectivity.
- The tree connectivity of regular complete bipartite graphs
- The minimal size of a graph with generalized connectivity _3=2
- On extremal graphs with internally disjoint Steiner trees
- scientific article; zbMATH DE number 165095 (Why is no real title available?)
- Note on the generalized connectivity.
- Two-tree graphs with minimum sum-connectivity index
- On extremal graphs with exactly one Steiner tree connecting any k vertices
- On the minimum size of graphs with given generalized connectivity
- On extremal graphs with at most internally disjoint Steiner trees connecting any n-1 vertices
This page was built for publication: The minimum size of a graph with given tree connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227103)
