BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Kelly's combinatorial lemma is a basic tool in the study of Ulam's reconstruction conjecture. A generalization in terms of a family of t-elements subsets of a v-element set was given by Pouzet. We consider a version of this generalization modulo a prime p. We give illustrations to graphs and tournaments.
Given a tournament T=(V,A), a subset X of V is an interval of T provided that for any a, b\in X and x\in V-X, (a,x) \in A if and only if (b,x)\in A. For example, \emptyset, \{x\} (x\in V) and V are intervals of T, called trivial intervals. A tournament, all the intervals of which are trivial, is indecomposable; otherwise, it is decomposable. A vertex x of an indecomposable tournament is critical if T-x is decomposable. In 1993, J.H. Schmerl and W.T. Trotter characterized the tournaments, all the vertices of which are critical, called critical tournaments. The cardinality of these tournaments is odd. Given an odd integer m \geq 5, there exist three critical tournaments of cardinality . and there are exactly three critical tournaments for each such a cardinality. In this article, we characterize the tournaments which admit a single non critical vertex, that we call (-1)-critical tournaments. The cardinality of these tournaments is odd. Given an odd integer m \geq 7, there exist 3m-15 (-1)-critical tournaments of cardinality m.
Let V be a set of cardinality v (possibly infinite). Two graphs G and G′ with vertex set V are {\it isomorphic up to complementation} if G′ is isomorphic to G or to the complement Gˉ of G. Let k be a non-negative integer, G and G′ are {\it k-hypomorphic up to complementation} if for every k-element subset K of V, the induced subgraphs G_↾K and G′_↾K are isomorphic up to complementation. A graph G is {\it k-reconstructible up to complementation} if every graph G′ which is k-hypomorphic to G up to complementation is in fact isomorphic to G up to complementation. We give a partial characterisation of the set S of pairs (n,k) such that two graphs G and G′ on the same set of n vertices are equal up to complementation whenever they are k-hypomorphic up to complementation. We prove in particular that S contains all pairs (n,k) such that 4≤k≤n−4. We also prove that 4 is the least integer k such that every graph G having a large number n of vertices is k-reconstructible up to complementation; this answers a question raised by P. Ille
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.