Reconstruction of the set of branches of a graph

DOI10.1007/BF01858446MaRDI QIDQ1911242zbMATH OpenOpenAlexFDO

Authors Andrew Vince, Yongzhi Yang

Publication date 29 September 1996

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01858446

zbMATH Keywords

branchpruned centerpruned graphreconstructionseparable graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

A \(k\)-vertex in a graph is a vertex of degree \(k\). The pruned graph \(\text{pruned} (G)\) of a separable graph \(G\) is the maximal subgraph of \(G\) having no 1-vertex. The block or cutpoint \(P\) of \(G\) which corresponds to the center of the block-cutpoint tree of \(\text{pruned} (G)\) is called the pruned center of \(G\). A branch \(B\) of \(G\) is a maximal subgraph of \(G\) that contains exactly one vertex \(u\) of the pruned center \(P\) such that \(B - u\) is connected. The reconstruction of the branches of \(G\) plays an important role in the reconstruction of \(G\). In this paper the authors improve upon a result of \textit{D. L. Greenwell} and \textit{R. L. Hemminger} [Many Facets of Graph Theory, Proc. Conf. Western Michigan Univ., Kalamazoo/Mi. 1968, 91-114 (1969; Zbl 0187.45601)] and prove that the branches of \(G\) are reconstructible except when all the following conditions hold: (i) \(\text{pruned} (G)\) is a vertex or an edge, (ii) \(G\) has exactly two branches, and (iii) one branch contains all 1-vertices of \(G\) and the other branch contains exactly one end-block. Further, they prove that in the extended case, the reconstruction of the branches is equivalent to the reconstruction of the graph itself. A related reference on reconstruction of separable graphs is [\textit{V. Krishnamoorthy} and \textit{K. R. Parthasarathy}, On the reconstruction conjecture for separable graphs, J. Aust. Math. Soc., Ser. A 30, 307-320 (1981; Zbl 0472.05047)].

Recommendations

• The centroidal branches of a separable graph are edge reconstructible
• Publication:3469127
• Two cases of reconstruction of separable graphs
• scientific article; zbMATH DE number 4208112
• Reconstructibility of graphs with a large branch: Permutation group theory and graph reconstruction
• scientific article; zbMATH DE number 637329
• All graphs are set reconstructible if all 2-connected graphs are set reconstructible.
• scientific article; zbMATH DE number 4079468
• scientific article; zbMATH DE number 4016946
• An extension of the Prüfer code and assembly of connected graphs from their blocks

Cites work

• scientific article; zbMATH DE number 3299378 (Why is no real title available?)
• On Ulam's conjecture for separable graphs
• Reconstructing Graphs
• Reconstruction of Cacti

Cited in

(4)

• Reconstructibility of graphs with a large branch: Permutation group theory and graph reconstruction
• The centroidal branches of a separable graph are edge reconstructible
• scientific article; zbMATH DE number 4135987 (Why is no real title available?)
• Two cases of reconstruction of separable graphs

This page was built for publication: Reconstruction of the set of branches of a graph

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