Edge-connectivity and edge-superconnectivity in sequence graphs

DOI10.1016/J.DAM.2007.05.006MaRDI QIDQ2384389zbMATH OpenOpenAlexFDO

Authors J. Fàbrega, C. Balbuena, P. García-Vázquez

Publication date 21 September 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.05.006

zbMATH Keywords

edge connectivityedge superconnectivitysequence graphs

Mathematics Subject Classification ID

Connectivity (05C40)

Review text

The vertex set of the sequence graph \(S_k(G)\) of a graph \(G\) is the set of all \(k\)-walks in \(G\), two vertices in \(S_k(G)\) are adjacent when corresponding walks are consecutive. Graph \(G\) is maximally edge-connected if the edge connectivity of \(G\) is equal to its minimum degree. A maximally edge-connected graph \(G\) is edge-superconnected if each minimum edge-cut consists of all edges incident with some vertex. In the paper are presented some sufficient conditions for the maximal edge-connectivity and edge-superconnectivity of sequence graphs.

Recommendations

• scientific article; zbMATH DE number 2191995
• Construction of super edge-connected multigraphs with prescribed degrees.
• Super Edge-Connected Linear Hypergraphs
• Sufficient conditions for maximally edge-connected and super-edge-connected graphs
• Degree sequence conditions for maximally edge-connected and super edge-connected hypergraphs

Cites work

• A sufficient condition for \(P_{k}\)-path graphs being \(r\)-connected
• Circulants and their connectivities
• Connectivity of iterated line graphs
• Edge-connectivity and super edge-connectivity of \(P_{2}\)-path graphs
• Edge-connectivity in \(P_k\)-path graphs
• Graphs on alphabets as models for large interconnection networks
• scientific article; zbMATH DE number 3859160 (Why is no real title available?)
• scientific article; zbMATH DE number 4162905 (Why is no real title available?)
• scientific article; zbMATH DE number 3735859 (Why is no real title available?)
• scientific article; zbMATH DE number 1744097 (Why is no real title available?)
• scientific article; zbMATH DE number 2197898 (Why is no real title available?)
• Line Digraph Iterations and the (d, k) Digraph Problem
• Maximally connected digraphs
• Path graphs
• Super edge-connectivity of dense digraphs and graphs
• Synthesis of reliable networks - a survey

Cited in

(2)

• scientific article; zbMATH DE number 5575580 (Why is no real title available?)
• scientific article; zbMATH DE number 4110725 (Why is no real title available?)

This page was built for publication: Edge-connectivity and edge-superconnectivity in sequence graphs

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