A solution to a conjecture on the generalized connectivity of graphs

DOI10.1007/s10878-015-9955-xzbMath1358.05159OpenAlexW2175201927WikidataQ122879028 ScholiaQ122879028MaRDI QIDQ512887

Meng-Meng Liu, Lily Chen, Yaping Mao, Xue Liang Li

Publication date: 3 March 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9955-x

zbMATH Keywords

complexityNP-completenesspolynomial-time algorithmgeneralized connectivitygeneralized edge connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Connectivity (05C40)

Related Items

Structure and substructure connectivity of alternating group graphs ⋮ Structure connectivity and substructure connectivity of split-star networks ⋮ Directed Steiner tree packing and directed tree connectivity ⋮ Reliability assessment of the divide-and-swap cube in terms of generalized connectivity ⋮ Connectivity, super connectivity and generalized 3-connectivity of folded divide-and-swap cubes ⋮ The reliability analysis based on the generalized connectivity in balanced hypercubes ⋮ The minimum size of a graph with given tree connectivity ⋮ Structure and substructure connectivity of balanced hypercubes ⋮ Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs ⋮ The generalized 4-connectivity of pancake graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On extremal graphs with at most \(\ell\) internally disjoint Steiner trees connecting any \(n-1\) vertices
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)
• The Steiner tree packing problem in VLSI design
• Packing Steiner trees: A cutting plane algorithm and computational results
• Note on the hardness of generalized connectivity
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• The generalized connectivity of complete equipartition 3-partite graphs
• The minimal size of a graph with given generalized 3-edge-connectivity
• On the generalized (edge-)connectivity of graphs
• Rainbow trees in graphs and generalized connectivity
• The generalized connectivity of complete bipartite graphs
• The generalized 3-connectivity of Lexicographic product graphs
• The generalized 3-connectivity of Cartesian product graphs