Degree conditions for vertex switching reconstruction
type: Item
instance of: scholarly article
title: Degree conditions for vertex switching reconstruction
zbMATH Open document ID: 0863.05056
DOI: 10.1016/0012-365X(95)00167-U
published in: Discrete Mathematics
publication date: 1997-05-20T00:00:00Z
review text: This paper is related to the \(s\)-vertex switching reconstruction problem. If \(G= G(V,E)\) is a graph and \(U \subset V\), the switching \(G_U\) of \(G\) is the graph obtained from \(G\) by replacing all the edges between \(U\) and \(V \backslash U\) with the nonedges. The \(s\)-switching deck of \(G\), denoted \(D_s(G)\), is the multiset of unlabeled graphs \(\{G_U: |U |=s\}\), and \(G\) is \(s\)-vertex switching reconstructible if it is determined up to isomorphism by \(D_s(G)\). The Krawtchouck polynomials \(K^n_s\) are defined by \[ K^n_s = \sum^s_{i=0} (-1)^i{x \choose i} {n-x \choose s-i} \] and have proved useful in vertex switching problems. In particular, it is known that if \(K^n_s\) has no even integer roots, then any \(n\) vertex graph is \(s\)-vertex switching reconstructible. The results in this paper deal with the case when \(K^n_s\) has even roots. Let \(\delta\) and \(\Delta\) be the minimum and maximum degrees of an \(n\) vertex graph \(G\), and let \(2r\) and \(2R\) be the smallest and largest even integer roots of \(K^n_s\). The main result of this paper is that if \[ \min \left({n-1 \choose \Delta}, {n-1 \choose \delta} \right) < {2^{n-2} \over n \sqrt {n+1}} {n\choose R-r}^{-1/2} {n \choose R+r}^{-1/2} \] then \(G\) is \(s\)-vertex switching reconstructible. A corollary to this result that does not involve the roots \(R\) and \(r\) is also proved, and states that if \[ \min \left({n-1 \choose \Delta}, {n-1 \choose \delta} \right) < {2^{n-2} \over n\sqrt {n+1}} {n\choose t}^{-1/2} {n \choose n/2}^{-1/2} \] where \(t= \sqrt {(s-1)(n-s+2)}\), then \(G\) is \(s\)-vertex switching reconstructible.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05E35
Mathematics Subject Classification ID: 33C55
zbMATH DE Number: 955164
zbMATH Keywords: switching reconstruction
zbMATH Keywords: Krawtchouck polynomials
zbMATH Keywords: vertex switching
author: Ilia Krasikov
reviewed by: Robert R. Molina
MaRDI profile type: Publication
cites work: Vertex-switching reconstruction of subgraph numbers and triangle-free graphs
cites work: Balance equations for reconstruction problems
cites work: A note on the vertex-switching reconstruction
cites work: Switching reconstruction and diophantine equations
cites work: More on vertex-switching reconstruction
cites work: Applications of balance equations to vertex switching reconstruction
cites work: Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
cites work: Q4146667
cites work: Q4105628
cites work: Reconstruction from vertex-switching
full work available at URL: 0012-365x(95)00167-u
OpenAlex ID: W2087164489
Recommended article: Reconstruction from vertex-switching
Recommended article: A note on the vertex-switching reconstruction
Recommended article: More on vertex-switching reconstruction
Recommended article: Applications of balance equations to vertex switching reconstruction
Recommended article: Vertex-switching reconstruction and folded cubes
Recommended article: Switching Reconstruction of Digraphs
Recommended article: Switching reconstruction of digraphs
Recommended article: Q4598369
Recommended article: Vertex-switching reconstruction of subgraph numbers and triangle-free graphs
Recommended article: Vertex reconstruction in Cayley graphs
description: scientific article; zbMATH DE number 955164