two examples on Graph theory Could anyone help me construct two examples:
1. a non-regular graph which has the property that the open neighborhoods of any two vertices do not contain each other?
2. minimal asymmetric graph which has the property that the open neighborhoods of any two vertices do not contain each other?
Thanks!
 A: The smallest (non-trivial) asymmetric graphs are listed in Wikipedia; they have 6 vertices, but each can be checked to not satisfy your extra condition:

Property P1: If $N_v$ and $N_u$ are the open neighbourhoods of two distinct vertices $v$ and $u$, then $N_v \not\subseteq N_u$.

(In some of these 6-vertex cases, this can be easily seen:  if there is a leaf node, then the condition is not satisfied.)  So the smallest possible (non-trivial) asymmetric graph that satisfies Property P1 must have 7 vertices; one example is given below.

Example 1: An asymmetric 7-vertex graph satisfying Property P1.


This is the smallest (in the sense of number of vertices) asymmetric graph for which Property P1 holds (except for trivial cases).  It's also not regular.  This example is far from unique.
However, we can define a slightly stronger property, which I think is a bit more natural.

Property P2: If $N_v$ and $N_u$ are the open neighbourhoods of two distinct vertices $v$ and $u$, then $N_v \not\subseteq N_u \cup \{u\}$.

Example 1 does not satisfy Property P2, e.g. when $v=1$ and $u=7$.  In fact, an exhaustive computer check reveals that no asymmetric 7-vertex graph satisfies Property P2.  So the smallest possible (non-trivial) asymmetric graph that satisfies Property P2 must have 8 vertices; one example is given below.

Example 2: An asymmetric 8-vertex graph satisfying Property P2.


Again, this is the smallest asymmetric graph for which Property P2 holds (except for trivial cases).  It's also not regular.  This is also unlikely to be unique (although I didn't check).
