2
$\begingroup$

This is the conjecture that inspired my question: https://en.wikipedia.org/wiki/Second_neighborhood_problem

For any vertex $v$, let $N(v)$ be the set of vertices adjacent to $v$ and let $N^2(v)$ the set 2nd order neighbors, thus all vertices that have a distance of exactly 2 relative to $v$. The conjecture concerns directed graphs, but I was interested in undirected simple graphs with each vertex having strictly more neighbors than second order neighbors. A basic example would be a graph of 4 vertices, completely connected except for one edge.

I believe such graphs are exactly the ones that have the following characteristic: for each vertex $v$, more than half of all possible 2-step walks starting from $v$ have an endpoint in $N(v)$

So far I haven't encountered a counter example but neither can I prove it, it's somewhat intuitive but not completely. Would love to hear your thoughts.

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

For an extreme counterexample, take $G = K_{n,n}$, the complete bipartite graph with $n$ vertices on each side. Here, $|N(v)|=n$ and $|N^2(v)| = n-1$ for all $v$, and none of the two-step walks from any vertex $v$ end up in $N(v)$.

$\endgroup$
9
  • $\begingroup$ Wow. That's extreme indeed, well spotted. You think the other direction might be actually correct or am I way off? Any other ideas for counter examples? $\endgroup$
    – AndroidBeginner
    Commented Jan 24, 2023 at 16:03
  • $\begingroup$ I think where all the easy-to-find examples are coming from are graphs with a large minimum degree (so $|N(v)| > |N^2(v)|$ because so many vertices are in $N(v)$ we don't have as many left for $|N^2(v)|$). I don't see why there should be a connection to how many $2$-step walks end up in $N(v)$. $\endgroup$
    – Misha Lavrov
    Commented Jan 24, 2023 at 16:12
  • $\begingroup$ Well you say you want a large minimum degree ( for every vertex thus). But then you will also get large $N^2(v)$ unless you route a part of these paths back to $N(v)$. You're counterexample surpassed this logic completely but I feel like it really was one in a kind in doing that. $\endgroup$
    – AndroidBeginner
    Commented Jan 24, 2023 at 16:40
  • $\begingroup$ No adjacent vertices can have a degree twice as high. That would really mess everything up as far as I can think of, agree? $\endgroup$
    – AndroidBeginner
    Commented Jan 24, 2023 at 18:44
  • $\begingroup$ The other way to get small $N^2(v)$ is for the neighbors of vertices in $N(v)$ to have a lot of overlap. (And, yes: if $v$ is adjacent to $w$ and $\deg(w) \ge 2 \deg(v)$, then the neighbors of $w$ not in $N(v)$ are on their own enough to make $N^2(v)$ as large as $N(v)$.) $\endgroup$
    – Misha Lavrov
    Commented Jan 24, 2023 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .