Maximally edge-connected and vertex-connected graphs and digraphs: A survey

DOI10.1016/j.disc.2007.06.035zbMath1160.05038OpenAlexW1969098266MaRDI QIDQ932603

Angelika Hellwig, Lutz Volkmann

Publication date: 11 July 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2007.06.035

zbMATH Keywords

diameterconnectivityline graphgirthclique numberminimum degreeedge-connectivitydegree sequencevertex-connectivityrestricted connectivityconditional connectivitylocal-edge-connectivitysuper-edge-connectivity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Toughness of the corona of two graphs ⋮ Sufficient conditions for \(k\)-restricted edge connected graphs ⋮ On edge cut of graphs leaving components of order at least five ⋮ On the edge-connectivity of C_4-free graphs ⋮ On the super‐restricted arc‐connectivity of s ‐geodetic digraphs ⋮ On restricted edge-connectivity of lexicographic product graphs ⋮ On the restricted arc-connectivity of \(s\)-geodetic digraphs ⋮ Super Edge-Connected Linear Hypergraphs ⋮ A kind of conditional fault tolerance of alternating group graphs ⋮ On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks ⋮ Optimally restricted edge connected elementary Harary graphs ⋮ The Menger number of the strong product of graphs ⋮ Sufficient Conditions for Maximally k-Isoperimetric Edge Connectivity of Graphs ⋮ Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number ⋮ Superconnectivity of graphs with odd girth \(g\) and even girth \(h\) ⋮ Sensor fault detection and isolation via networked estimation: rank-deficient dynamical systems ⋮ Some properties of subgroup complementary addition Cayley graphs on abelian groups ⋮ Uniformly optimally reliable graphs: A survey ⋮ On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs ⋮ Degree sequence conditions for maximally edge-connected and super edge-connected hypergraphs ⋮ Restricted arc connectivity of unidirectional hypercubes and unidirectional folded hypercubes ⋮ Maximally connected \(p\)-partite uniform hypergraphs ⋮ On super 2-restricted and 3-restricted edge-connected vertex transitive graphs ⋮ Edge fault tolerance of graphs with respect to super edge connectivity ⋮ On optimizing edge connectivity of product graphs ⋮ Maximally edge‐connected realizations and Kundu's k $k$‐factor theorem ⋮ The edge‐connectivity of vertex‐transitive hypergraphs ⋮ Restricted arc-connectivity of unidirectional star graphs ⋮ Game connectivity of graphs ⋮ Super-connected but not super edge-connected graphs ⋮ Super restricted edge connectivity of regular edge-transitive graphs ⋮ On the connectivity of \(p\)-diamond-free vertex transitive graphs ⋮ Super restricted edge connectivity of regular graphs with two orbits ⋮ On computing of a conditional edge connectivity of alternating group network ⋮ Codes from incidence matrices of graphs ⋮ Edge fault-tolerance analysis of maximally edge-connected graphs and super edge-connected graphs ⋮ Edge-fault-tolerant strong Menger edge connectivity on regular graphs ⋮ The minimum restricted edge-connected graph and the minimum size of graphs with a given edge-degree ⋮ Sufficient conditions for maximally restricted edge connected graphs ⋮ Edge fault tolerance of super edge connectivity for three families of interconnection networks ⋮ \(\lambda^{\prime}\)-optimality of bipartite digraphs ⋮ Sufficient conditions for maximally edge-connected and super-edge-connected graphs depending on the clique number ⋮ On average connectivity of the strong product of graphs ⋮ A sufficient condition for graphs to be \(\lambda_k\)-optimal ⋮ The \(k\)-restricted edge connectivity of balanced bipartite graphs ⋮ A kind of conditional connectivity of Cayley graphs generated by unicyclic graphs ⋮ Inverse degree and super edge-connectivity ⋮ Maximally edge-connected hypergraphs ⋮ The critical node detection problem in networks: a survey ⋮ Edge fault tolerance of interconnection networks with respect to maximally edge-connectivity ⋮ Connectivity of generating graphs of nilpotent groups ⋮ On the connectivity and superconnected graphs with small diameter ⋮ The \(p\)-restricted edge-connectivity of Kneser graphs ⋮ Vulnerability of super extra edge-connected graphs ⋮ 3-restricted arc connectivity of digraphs ⋮ Cyclic arc-connectivity in a Cartesian product digraph ⋮ \(\lambda ^{\prime}\)-optimal digraphs ⋮ On local connectivity of graphs with given clique number ⋮ On the edge-connectivity of graphs with two orbits of the same size ⋮ Sufficient conditions for a graph to be λ _k -optimal with given girth and diameter ⋮ Vertex fault tolerance of optimal-\(\kappa \) graphs and super-\(\kappa \) graphs ⋮ Sufficient conditions for maximally edge-connected hypergraphs ⋮ Sufficient conditions on the zeroth-order general Randić index for maximally edge-connected graphs ⋮ Super \(p\)-restricted edge connectivity of line graphs ⋮ Sufficient conditions for maximally edge-connected and super-edge-connected digraphs depending on the size ⋮ Degree conditions for graphs to be \(\lambda_3\)-optimal and super-\(\lambda _3\) ⋮ Edge-connectivity in hypergraphs ⋮ Minimally 3-restricted edge connected graphs ⋮ A neighborhood condition for graphs to be maximally \(k\)-restricted edge connected ⋮ Connectivity of Cartesian product of hypergraphs ⋮ Sufficient conditions for bipartite graphs to be super-\(k\)-restricted edge connected ⋮ On the connectivity of \(p\)-diamond-free graphs ⋮ On the Superconnectivity in graphs with odd girth g and even girth h ⋮ Sufficient conditions for hypergraphs to be maximally edge-connected ⋮ On the conditional edge connectivity of double-orbit graphs ⋮ Star complements and edge-connectivity in finite graphs ⋮ Onm-restricted edge connectivity of undirected generalized De Bruijn graphs ⋮ Maximally and super connected multisplit graphs and digraphs ⋮ On the optimality of 3-restricted arc connectivity for digraphs and bipartite digraphs ⋮ Realizability of fault-tolerant graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the vertex-connectivity of digraphs and graphs
• 3-restricted edge cut of graphs
• Optimization problems of the third edge-connectivity of graphs
• Connectivity of graphs with given girth pair
• Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal
• Lower connectivities of regular graphs with small diameter
• On the connectivity of cages with girth five, six and eight
• The connectivity of a graph and its complement
• On the existence of edge cuts leaving several large components
• Degree sequence conditions for maximally edge-connected oriented graphs
• Super connectivity of line graphs
• Sufficient conditions for \(\lambda ^{\prime}\)-optimality of graphs with small conditional diameter
• The connectivity of strongly regular graphs
• Sufficient conditions for maximally connected dense graphs
• On computing a conditional edge-connectivity of a graph
• On graphs with equal edge connectivity and minimum degree
• Super edge-connectivity of dense digraphs and graphs
• Degree realization of undirected graphs in reduced form
• On the connectivity of Cayley graphs
• On graphs with equal edge-connectivity and minimum degree
• \((k,g)\)-cages are 3-connected
• The superconnectivity of large digraphs and graphs
• Extraconnectivity of graphs with large girth
• On the distance connectivity of graphs and digraphs
• A sufficient condition for equality of arc-connectivity and minimum degree of a digraph
• On a kind of restricted edge connectivity of graphs
• Claw-free graphs---a survey
• On the order and size of \(s\)-geodetic digraphs with given connectivity
• Results on the edge-connectivity of graphs
• Super-connectivity and super-edge-connectivity for some interconnection networks
• Bound on \(m\)-restricted edge connectivity
• Super restricted edge-connectivity of vertex-transitive graphs
• Cuts leaving components of given minimum order
• Sufficient conditions for \(\lambda'\)-optimality in graphs of diameter 2
• On the construction of most reliable networks
• On the superconnectivity of generalized \(p\)-cycles
• Edge-cuts leaving components of order at least three
• Conditional edge connectivity properties, reliability comparisons and transitivity of graphs
• Optimally super-edge-connected transitive graphs
• A note on the edge-connectivity of cages
• Neighborhood and degree conditions for super-edge-connected bipartite digraphs
• On the extraconnectivity of graphs
• Bipartite graphs and digraphs with maximum connectivity
• Degree sequence conditions for maximally edge-connected graphs depending on the clique number
• On the connectivity of Cayley digraphs
• Restricted arc-connectivity of digraphs
• On the connectivity of diamond-free graphs
• Note on the connectivity of line graphs
• Sufficient conditions for restricted-edge-connectivity to be optimal
• Local-edge-connectivity in digraphs and oriented graphs
• On local connectivity of graphs
• On optimally-\(\lambda^{(3)}\) transitive graphs
• Super restricted edge connectivity of regular graphs
• The connectivity of line-graphs
• On the line-connectivity of line-graphs
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• Über den Zusammenhang symmetrischer Graphen
• On a theorem of Chartrand, Kapoor and Kronk
• (\(\delta ,g\))-cages with \(g\geqslant 10\) are 4-connected
• Upper bound on the third edge-connectivity of graphs
• A proof of an inequality concerning \(k\)-restricted edge connectivity
• Edge cuts leaving components of order at least \(m\)
• Selbstkomplementäre Graphen
• On the superconnectivity and the conditional diameter of graphs and digraphs
• A sufficient condition for equality of edge-connectivity and minimum degree of a graph
• Connectivity of Regular Directed Graphs with Small Diameters
• Circulants and their connectivities
• On super edge-connectivity of Cartesian product graphs
• Sufficient conditions for graphs to be λ′‐optimal and super‐λ′
• On unreliability polynomials and graph connectivity in reliable network synthesis
• Cyclic sums, network sharing, and restricted edge cuts in graphs with long cycles
• Conditional connectivity
• The Diameter of a Graph and its Complement
• Super Line-Connectivity Properties of Circulant Graphs
• Lower-bounds on the connectivities of a graph
• Graphs with prescribed connectivity and line graph connectivity
• The connectivities of line and total graphs
• Cages—a survey
• Vertex Transitivity and Super Line Connectedness
• On super-edge-connected digraphs and bipartite digraphs
• A Generalization of Line Connectivity and Optimally Invulnerable Graphs
• A homology theory for spanning tress of a graph
• A Lower Bound on the Number of Vertices of a Graph
• Maximally connected digraphs
• Super edge connectivity properties of connected edge symmetric graphs
• Sufficient conditions for equality of connectivity and minimum degree of a graph
• On super i‐connected graphs
• Connectivity of cages
• Edge-superconnectivity of cages
• Superconnected digraphs and graphs with small conditional diameters
• Fault tolerance measures for m-ary n-dimensional hypercubes based on forbidden faulty sets
• All (k;g)-cages arek-edge-connected
• Sufficient conditions for graphs to be ??-optimal, super-edge-connected, and maximally edge-connected
• On restricted connectivities of permutation graphs
• The connectivity of large digraphs and graphs
• Edge‐connectivity in p‐partite graphs
• Super edge- and point-connectivities of the Cartesian product of regular graphs
• Degree sequence conditions for equal edge‐connectivity and minimum degree, depending on the clique number
• All (k;g)‐cages are edge‐superconnected
• On connectivity in graphs with given clique number
• Sufficient conditions for λ′‐optimality in graphs with girth g
• A Graph-Theoretic Approach to a Communications Problem
• A Lower Bound for the Number of Vertices of a Graph
• A sufficient condition for n ‐connectedness of graphs
• Connectivity of transitive graphs
• Asymptotic Formulas for the Probability of k-Connectedness of Random Graphs
• On restricted edge-connectivity of graphs.

This page was built for publication: Maximally edge-connected and vertex-connected graphs and digraphs: A survey