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