The \((\leq k)\)-half-reconstructability of graphs for \(7\leq k\leq 12\).
type: Item
instance of: scholarly article
zbMATH Open document ID: 1389.05113
author: Nadia El Amri
publication date: 2016-10-26T00:00:00Z
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 6644069
zbMATH Keywords: \((\leq k)\)-half-reconstructable graphs
zbMATH Keywords: \((\leq k)\)-hypomorphic graphs
zbMATH Keywords: hemimorphic graphs
MaRDI profile type: Publication
Recommended article: The (\(\leqslant k\))-half-reconstructibility of graphs for \(k\in \{11,12\}\)
Recommended article: The \((\leq 6)\)-half-reconstructibility of digraphs
Recommended article: Q3504736
Recommended article: Q3335821
Recommended article: Q3765814
Recommended article: Q4552168
Recommended article: On Reconstructing Graphs and Their Complements
Recommended article: Q3469125
Recommended article: Q4316714
Recommended article: Seven Problems on Hypohamiltonian and Almost Hypohamiltonian Graphs
title: The \((\leq k)\)-half-reconstructability of graphs for \(7\leq k\leq 12\).
published in: Ars Combinatoria
review text: The dual of a directed graph \(G=(V,A)\) is the directed graph \(G^*=(V,A^*)\) with \(A^*=\{ (y,x):(x,y)\in A\}\). Two directed graphs \(G=(V,A)\) and \(G'=(V',A')\) are called dually isomorphic iff \(G^*\) and \(G'\) are isomorphic. They are called hemimorphic iff they are isomorphic or dually isomorphic. Two directed graphs \(G=(V,A)\) and \(G'=(V,A')\) on the same vertex set \(V\) are called \((\leq k)\)-hypomorphic (hemimorphic) iff, for all \(X\subset V\) with \(|X|\leq k\), we have that the induced directed subgraphs \(G[X]\) and \(G'[X]\) are isomorphic (hemimorphic). A directed graph \(G=(V,A)\) is called \(\leq k\)-(half-)reconstructible iff, for all \((\leq k)\)-hypomorphic (hemimorphic) directed graphs \(G'\), we have that \(G\) is isomorphic (hemimorphic) to \(G'\).NEWLINENEWLINE Finite directed graphs are known to be \((\leq 12)\)-half-reconstructible and, for \(7\leq k\leq 11\), the \((\leq k)\)-half-reconstructible finite directed graphs have been characterized. The present paper characterizes, for \(7\leq k\leq 12\), all \((\leq k)\)-half-reconstructible directed graphs. As is the case with many results on reconstruction, statements and proofs can become quite technical. Because the paper extends characterizations from the finite to the infinite scenario, it requires extensive quotes from the literature, which are summarized in pages 195 to 201.NEWLINENEWLINE A chain is a directed graph whose arcs comprise a transitive relation such that any two vertices are joined by an arc. A directed graph on vertices \(\{ v_j : j\in \mathbb{N}\}\) such that either, for any two non-consecutive integers \(i\) and \(k\), we have that neither \((v_i,v_k)\) nor \((v_k,v_i)\) is an arc, or, such that, for any two non-consecutive integers \(i\) and \(k\), we have that both \((v_i,v_k)\) and \((v_k,v_i)\) are arcs is called a potentially augmented semi-infinite path (consécutivité infinies à une seule extrémité) iff either, for all \(j\in\mathbb{N}\), we have that \((v_j…
reviewed by: Bernd Schröder
description: scientific article; zbMATH DE number 6644069