Suggest a Book

# Diameter and low-degree vertex

Level: unknown

posted Jul 28 '12

Chandra Chekuri
51 1 5
Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...
1. Let $G = (V,E)$ be an undirected connected graph. Suppose $G$ has a pair of nodes $s,t$ that are distance $d$ apart. Show that there is a vertex $v\in G$ such that the degree of $v$ is at most $6n/d$ where $n = |V|$.
2. Show that for directed graphs the above is not true. More precisely, give an example of a directed graph on $n$ nodes such that there is a pair of nodes $s, t$ such that distance from $s$ to $t$ is $\Omega(n)$ and for each node $v$ in the graph, both the in-degree and out-degree are $\Omega(n)$.
delete retag edit

## Stats

Posted: Jul 28 '12

Seen: 129 times

Last updated: Oct 22 '12