Non-separable detachments of graphs

DOI10.1016/S0095-8956(02)00026-6MaRDI QIDQ1403909zbMATH OpenOpenAlexFDO

Authors Bill Jackson, Tibor Jordán

Publication date 20 August 2003

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0095-8956(02)00026-6

zbMATH Keywords

degree specificationdetachmentedge-connectivity

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Review text

Let \(G=(V,E)\) be a graph (loops and multiple edges permitted) and let \(r:V\to Z_+\). An \(r\)-detachment of \(G\) is a graph \(H\) whose vertices are obtained by splitting each vertex \(v\in V\) into \(r(v)\) vertices, called the pieces of \(v\); each edge \(uv\in E\) corresponds to an edge of \(H\) joining a piece of \(u\) to a piece of \(v\). An \(r\)-degree specification for \(G\) is a function \(f\) on \(V\) such that \(f(v)\) is a partition of the valence of \(v\) into \(r(v)\) positive integers. An \(f\)-detachment of \(G\) is an \(r\)-detachment in which the valences of the pieces of each \(v\in V\) are given by \(f(v)\). The authors answer a question posed by \textit{C. St. J. A. Nash-Williams} [Surveys in combinatorics 1985, Proc. 10th British Combin. Conf., Glasgow/Scotl. 1985, Lond. Math. Soc. Lect. Note Ser. 103, 137-151 (1985; Zbl 0573.05054)] by giving necessary and sufficient conditions on a graph \(G=(V,E)\) and a function \(r:V\to Z_+\) for the existence of a cut-vertex-free \(r\)-detachment of \(G\). Furthermore, an analogous result is obtained for the existence of a cut-vertex-free \(f\)-detachment.

Recommendations

• Highly edge-connected detachments of graphs and digraphs
• Detachments Preserving Local Edge-Connectivity of Graphs
• Another proof of a theorem concerning detachments of graphs
• Amalgamations of almost regular edge-colourings of simple graphs
• Connected Detachments of Graphs and Generalized Euler Trails
• Fragile graphs with small independent cuts
• The connected cutset connectivity of a graph
• A note on fragile graphs
• Decomposition of a 2-connected graph into three connected subgraphs
• Detachments of Complete Graphs

Cites work

• Connected Detachments of Graphs and Generalized Euler Trails
• scientific article; zbMATH DE number 3914375 (Why is no real title available?)
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I

Cited in

(10)

• A detachment algorithm for inferring a graph from path frequency
• Enumeration of the degree sequences of non-separable graphs and connected graphs
• Another proof of a theorem concerning detachments of graphs
• Independence free graphs and vertex connectivity augmentation
• Orientations and detachments of graphs with prescribed degrees and connectivity
• Multiply balanced edge colorings of multigraphs
• scientific article; zbMATH DE number 3914375 (Why is no real title available?)
• Detachments of Complete Graphs
• Highly edge-connected detachments of graphs and digraphs
• scientific article; zbMATH DE number 842894 (Why is no real title available?)

This page was built for publication: Non-separable detachments of graphs

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