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
    Slight language clarification: should the condition be interpreted as "the open neighbourhood of any point does not contain the open neighbourhood of any other point", or "the open neighbourhoods of any two points are not equal"?2011-05-15
  • 0
    Or does it mean the open neighbourhoods do not intersect? In which case property 1 sounds like "being Hausdorff" (and non-regular).2011-05-15
  • 0
    Also why do you care about the graph being non-regular in 1. it doesn't seem to add much.2011-05-15
  • 0
    to IainM: the condition is "the open neighbourhood of any point does not contain the open neighbourhood of any other point"2011-05-16
  • 0
    to David Kohler, I know that Frucht graph holds for the condition, I wonder if 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).