Graphs with large generalized (edge-)connectivity

DOI10.7151/DMGT.1907zbMATH Open1350.05080arXiv1305.1089OpenAlexW2963493011MaRDI QIDQ339485FDOQ339485

Yaping Mao, Xueliang Li

Publication date: 11 November 2016

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: The generalized $k$-connectivity $kapp{a}_k(G)$ of a graph $G$, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized $k$-edge-connectivity $lambd{a}_k(G)$. In this paper, graphs of order $n$ such that $kapp{a}_k(G)=n-frack2-1$ and $lambd{a}_k(G)=n-frack2-1$ for even $k$ are characterized.

Full work available at URL: https://arxiv.org/abs/1305.1089

Recommendations

• On the generalized (edge-)connectivity of graphs
• Sharp upper bounds for generalized edge-connectivity of product graphs
• A result on the 3-generalized connectivity of a graph and its line graph
• The generalized connectivity of the line graph and the total graph for the complete bipartite graph
• A solution to a conjecture on the generalized connectivity of graphs

zbMATH Keywords

packingSteiner treeedge connectivityedge-disjoint treesgeneralized edge-connectivityinternally disjoint trees

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• The generalized connectivity of complete equipartition 3-partite graphs
• Rainbow trees in graphs and generalized connectivity
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• On extremal graphs with internally disjoint Steiner trees
• Title not available (Why is that?)
• On extremal graphs with at most \(\ell\) internally disjoint Steiner trees connecting any \(n-1\) vertices
• Edge-disjoint trees containing some given vertices in a graph
• Packing of Steiner trees and \(S\)-connectors in graphs
• Über die Maximalzahl kreuzungsfreier H-Wege
• Pendant tree-connectivity
• Path-connectivity in graphs
• On the \(\ell\)-connectivity of a graph
• Über die Maximalzahl kantendisjunkter A-Wege
• 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
• Note on the spanning-tree packing number of lexicographic product graphs
• The minimal size of a graph with given generalized 3-edge-connectivity.
• On the generalized (edge-)connectivity of graphs
• Topics in structural graph theory
• Title not available (Why is that?)
• Edge disjoint Steiner trees in graphs without large bridges
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Generalization of Line Connectivity and Optimally Invulnerable Graphs
• Separation of graphs into three components by the removal of edges
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs with large generalized 3-connectivity
• The generalized 3-connectivity of Lexicographic product graphs
• The generalized 3-connectivity of Cartesian product graphs
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)

Cited In (10)

• Structure and substructure connectivity of balanced hypercubes
• Constructing edge-disjoint Steiner paths in lexicographic product networks
• Title not available (Why is that?)
• Generalized Connectivity of Graphs
• The minimum size of a graph with given tree connectivity
• Title not available (Why is that?)
• Structure and substructure connectivity of alternating group graphs
• Title not available (Why is that?)
• Path 3-(edge-)connectivity of lexicographic product graphs
• Extraconnectivity of graphs with large minimum degree and girth

This page was built for publication: Graphs with large generalized (edge-)connectivity

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