Graphs with large generalized (edge-)connectivity

DOI10.7151/DMGT.1907MaRDI QIDQ339485zbMATH OpenOpenAlexFDO

Authors Yaping Mao, Xueliang Li

Publication date 11 November 2016

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4070940 (Why is no real title available?)
• scientific article; zbMATH DE number 3706492 (Why is no real title available?)
• scientific article; zbMATH DE number 3773644 (Why is no real title available?)
• scientific article; zbMATH DE number 30760 (Why is no real title available?)
• scientific article; zbMATH DE number 1321108 (Why is no real title available?)
• scientific article; zbMATH DE number 1146232 (Why is no real title available?)
• scientific article; zbMATH DE number 1161250 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• A Generalization of Line Connectivity and Optimally Invulnerable Graphs
• Edge disjoint Steiner trees in graphs without large bridges
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-disjoint trees containing some given vertices in a graph
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• Note on the generalized connectivity.
• Note on the hardness of generalized connectivity
• Note on the spanning-tree packing number of lexicographic product graphs
• On extremal graphs with at most \(\ell\) internally disjoint Steiner trees connecting any \(n-1\) vertices
• On extremal graphs with internally disjoint Steiner trees
• On the Problem of Decomposing a Graph into n Connected Factors
• On the \(\ell\)-connectivity of a graph
• On the generalized (edge-)connectivity of graphs
• Packing Steiner trees: A cutting plane algorithm and computational results
• Packing of Steiner trees and \(S\)-connectors in graphs
• Path-connectivity in graphs
• Pendant tree-connectivity
• Rainbow trees in graphs and generalized connectivity
• Separation of graphs into three components by the removal of edges
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)
• The Steiner tree packing problem in VLSI design
• The generalized 3-connectivity of Cartesian product
• The generalized 3-connectivity of lexicographic product graphs
• The generalized connectivity of complete equipartition 3-partite graphs
• The minimal size of a graph with given generalized 3-edge-connectivity.
• The tree connectivity of regular complete bipartite graphs
• Topics in structural graph theory
• Über die Maximalzahl kantendisjunkter A-Wege
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(18)

• Path 3-(edge-)connectivity of lexicographic product graphs
• Structure and substructure connectivity of alternating group graphs
• scientific article; zbMATH DE number 4101244 (Why is no real title available?)
• On the difference of two generalized connectivities of a graph
• Extraconnectivity of graphs with large minimum degree and girth
• The generalized connectivity of complete bipartite graphs.
• A new measure of graph connectivity
• scientific article; zbMATH DE number 3867370 (Why is no real title available?)
• Structure and substructure connectivity of balanced hypercubes
• The minimum size of a graph with given tree connectivity
• scientific article; zbMATH DE number 5642607 (Why is no real title available?)
• On the generalized (edge-)connectivity of graphs
• Note for the conjecture on the generalized 4-connectivity of total graphs of the complete bipartite graph
• Generalized Connectivity of Graphs
• Constructing edge-disjoint Steiner paths in lexicographic product networks
• On the maximum and minimum sizes of a graph with given \(k\)-connectivity
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• A solution to a conjecture on the generalized connectivity of graphs

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)