The Minimum Size of a Graph with Given Tree Connectivity
For a graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-tree is a such subgraph T of G that is a tree with S ⊆ V (T). Two S-trees T1 and T2 are said to be internally disjoint if E(T1) ∩ E(T2) = ∅ and V (T1) ∩ V (T2) = S, and edge-disjoint if E(T1) ∩ E(T2) = ∅. The generalized local con...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2021-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2193 |
| _version_ | 1797704393884172288 |
|---|---|
| author | Sun Yuefang Sheng Bin Jin Zemin |
| author_facet | Sun Yuefang Sheng Bin Jin Zemin |
| author_sort | Sun Yuefang |
| collection | DOAJ |
| description | For a graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-tree is a such subgraph T of G that is a tree with S ⊆ V (T). Two S-trees T1 and T2 are said to be internally disjoint if E(T1) ∩ E(T2) = ∅ and V (T1) ∩ V (T2) = S, and edge-disjoint if E(T1) ∩ E(T2) = ∅. The generalized local connectivity κG(S) (generalized local edge-connectivity λG(S), respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) S-trees in G. For an integer k with 2 ≤ k ≤ n, the generalized k-connectivity (generalized k-edge-connectivity, respectively) is defined as κk(G) = min{κG (S) | S ⊆ V (G), |S| = k} (λk(G) = min{λG(S) | S ⊆ V (G), |S| = k}, respectively). |
| first_indexed | 2024-03-12T05:19:43Z |
| format | Article |
| id | doaj.art-6ba6691ec13748a99c6f24d786d131db |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:19:43Z |
| publishDate | 2021-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-6ba6691ec13748a99c6f24d786d131db2023-09-03T07:47:16ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922021-05-0141240942510.7151/dmgt.2193The Minimum Size of a Graph with Given Tree ConnectivitySun Yuefang0Sheng Bin1Jin Zemin2Department of Mathematics, Shaoxing UniversityZhejiang312000, P.R. ChinaCollege of Computer Science and TechnologyNanjing University of Aeronautics and AstronauticsJiangsu211100, ChinaDepartment of Mathematics, Zhejiang Normal UniversityZhejiang321004, P.R. ChinaFor a graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-tree is a such subgraph T of G that is a tree with S ⊆ V (T). Two S-trees T1 and T2 are said to be internally disjoint if E(T1) ∩ E(T2) = ∅ and V (T1) ∩ V (T2) = S, and edge-disjoint if E(T1) ∩ E(T2) = ∅. The generalized local connectivity κG(S) (generalized local edge-connectivity λG(S), respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) S-trees in G. For an integer k with 2 ≤ k ≤ n, the generalized k-connectivity (generalized k-edge-connectivity, respectively) is defined as κk(G) = min{κG (S) | S ⊆ V (G), |S| = k} (λk(G) = min{λG(S) | S ⊆ V (G), |S| = k}, respectively).https://doi.org/10.7151/dmgt.2193generalized connectivitytree connectivitygeneralized k-connectivitygeneralized k-edge-connectivitypacking05c0505c3505c4005c70 |
| spellingShingle | Sun Yuefang Sheng Bin Jin Zemin The Minimum Size of a Graph with Given Tree Connectivity Discussiones Mathematicae Graph Theory generalized connectivity tree connectivity generalized k-connectivity generalized k-edge-connectivity packing 05c05 05c35 05c40 05c70 |
| title | The Minimum Size of a Graph with Given Tree Connectivity |
| title_full | The Minimum Size of a Graph with Given Tree Connectivity |
| title_fullStr | The Minimum Size of a Graph with Given Tree Connectivity |
| title_full_unstemmed | The Minimum Size of a Graph with Given Tree Connectivity |
| title_short | The Minimum Size of a Graph with Given Tree Connectivity |
| title_sort | minimum size of a graph with given tree connectivity |
| topic | generalized connectivity tree connectivity generalized k-connectivity generalized k-edge-connectivity packing 05c05 05c35 05c40 05c70 |
| url | https://doi.org/10.7151/dmgt.2193 |
| work_keys_str_mv | AT sunyuefang theminimumsizeofagraphwithgiventreeconnectivity AT shengbin theminimumsizeofagraphwithgiventreeconnectivity AT jinzemin theminimumsizeofagraphwithgiventreeconnectivity AT sunyuefang minimumsizeofagraphwithgiventreeconnectivity AT shengbin minimumsizeofagraphwithgiventreeconnectivity AT jinzemin minimumsizeofagraphwithgiventreeconnectivity |