4
$\begingroup$

Suppose $B$ is a bipartite graph on $n$ vertices with minimum degree $\delta$. It can be shown fairly easily that if $4 \delta >n$, we have the nice property that any two vertices in the same bipartition of $B$ must share at least one common neighbor.

In this question, we look at a generalization. Suppose we have an arbitrary graph $G$ on $n$ vertices. Is there a "big enough" value of $\delta$ so that any two vertices not connected by an edge must share a common neighbor (i.e. if $k\cdot \delta >n$, this property holds).

Now, what if we start putting restrictions on $G$. We know that if $G$ is bipartite, $k=4$ does in fact suffice. But what if we say $G$ is triangle free,or 5-cycle free. What can we say about $k$.

Any help would be great, tell me if I was confusing anywhere!

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ $k=4$ suffices only with the condition that the vertices are in the same bipartition, not in general. In general, the best you can say is that among two distinct vertices in a graph not joined by an edge, a sufficient condition is that the sum of their degrees must be at least n-1 for them to have a common neighbor, from which you can infer a sufficient condition on $\delta$. It is not clear if you want to characterize subclasses of graphs of diameter two or if you want to know more about the role of $\delta$ with respect to certain graph properties. $\endgroup$
    – The Masked Avenger
    Jul 24, 2013 at 18:58
  • $\begingroup$ Also, if the graph has diameter 2 and no cycles of length 5 or smaller, then the graph is acyclic and easily characterized. You probably want to look at diameter 2 graphs before speculating on $k$. $\endgroup$
    – The Masked Avenger
    Jul 24, 2013 at 19:13
  • 2
    $\begingroup$ Diameter 2 graphs are precisely the graphs with this property, no? So you're saying if the graph has this property and has girth >5, it necessarily follows the graph is acyclic (i.e. a tree)? $\endgroup$
    – Anand
    Jul 24, 2013 at 19:41
  • $\begingroup$ Going in another direction, star graphs have minimum degree 1 and satisfy your property. $\endgroup$
    – user25199
    Jul 24, 2013 at 21:48
  • $\begingroup$ I don't know if girth is defined for trees. If you look at a cycle and consider two diametrically opposite points, they must share a neighbor if the graph has diameter 2. This means these same two points are on a cycle of length less than the cycle being considered, and eventually on a cycle of length at most 5. $\endgroup$
    – The Masked Avenger
    Jul 24, 2013 at 22:11

1 Answer 1

Reset to default
1
$\begingroup$

I very much doubt such a statement is possible. As people have pointed out, your property is what is usually called "diameter equal to two". The Paley graphs are a family where the degree is $\approx \frac{n}{2}$ but they have diameter two.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.