Name
Abstract | ||
|---|---|---|
Let S be a set of at least two vertices in a graph G. A subtree T of G is a S-Steiner tree if S⊆V(T). Two S-Steiner trees T1 and T2 are edge-disjoint (resp. internally vertex-disjoint) if E(T1)∩E(T2)=∅ (resp. E(T1)∩E(T2)=∅ and V(T1)∩V(T2)=S). Let λG(S) (resp. κG(S)) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S-Steiner trees in G, and let λk(G) (resp. κk(G)) be the minimum λG(S) (resp. κG(S)) for S ranges over all k-subset of V(G). Kriesell conjectured that if λG({x,y})≥2k for any x,y∈S, then λG(S)≥k. He proved that the conjecture holds for |S|=3,4. In this paper, we give a short proof of Kriesell’s Conjecture for |S|=3,4, and also show that λk(G)≥1k−1kℓ2 (resp. κk(G)≥1k−1kℓ2 ) if λ(G)≥ℓ (resp. κ(G)≥ℓ) in G, where k=3,4. Moreover, we also study the relation between κk(L(G)) and λk(G), where L(G) is the line graph of G. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.disc.2018.03.021 | Discrete Mathematics |
Keywords | Field | DocType |
Connectivity,Edge-connectivity,Packing Steiner trees,Tree connectivity,Line graph | Discrete mathematics,Graph,Combinatorics,Line graph,Vertex (geometry),Steiner tree problem,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
341 | 7 | 0012-365X |
Citations | PageRank | References |
5 | 0.47 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hengzhe Li | 1 | 81 | 9.29 |
| Baoyindureng Wu | 2 | 99 | 24.68 |
| Jixiang Meng | 3 | 353 | 55.62 |
| Yingbin Ma | 4 | 8 | 3.27 |