2
$\begingroup$

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!

  • 0
    to David Kohler, I know that Frucht graph holds $f$or the condition, I wonder i$f$ there exists non-regular graph which holds the conditon.2011-05-16

1 Answers 1

3

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.

Asymmetric 7-vertex graph satisfying P<sub>1</sub>

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.

Asymmetric 8-vertex graph satisfying P<sub>2</sub>

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).