Hypomorphy of graphs up to complementation

Details Hypomorphy of graphs up to complementation Hypomorphy of graphs up to complementation

2006-01-06

arxiv.org/abs/math/0601118v1

Mathematics

Combinatorics

Scientific paper

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 $\bar 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\_{\restriction K}$ and $G'\_{\restriction 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 $\mathcal 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 $\mathcal S$ contains all pairs $(n,k)$ such that $4\leq k\leq 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

Affiliated with

Also associated with

No associations

Rating

Hypomorphy of graphs up to complementation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hypomorphy of graphs up to complementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypomorphy of graphs up to complementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-110489