All Questions
5 questions
-1
votes
1
answer
111
views
Smallest $k$ to make sure the $k$-nearest-neighbor graph is connected
Given any $n$ points in $\mathbb{R}^d$, then make an undirected edge between every point and each of its $k$ nearest neighbors (in Euclidean distance). What is the smallest $k$ to make sure that the ...
- 2,066
1
vote
2
answers
2k
views
counting allowable/admissible paths on a grid with obstacles
I have a grid where some paths are removed.
where the following path is admissible,
but this path
is not.
How can I go about finding how many admissible paths are there on the following 2 grids (...
- 327
4
votes
1
answer
619
views
A question regarding a $k$-connected graph
I would like to show several things, some for general $k$-connected graphs and some for several instances ($k=2,3,...$).
First, I want to show that for every $k$-connected graph each subset $A\...
- 799
1
vote
1
answer
261
views
How to count number of vertices in a particular graph.
Let $4\leq r\leq \lfloor\frac{n}{2}\rfloor$ and $P_n$ be a path graph on $n\geq 2r$ vertices.
$V(P_n) = \{v_1,\ldots,v_n\}$.
We obtain a graph $H$ by adding a vertex $x$ to $P_n$ such that $x$ is ...
- 4,648
1
vote
0
answers
509
views
Proving vertex form of Menger's Theorem et al. without using capacity of vertices.
I'm teaching an undergrad course in graph theory and have just finished the proof of Max Flow/Min Cut. So far I have used Diestel's definition (more or less) of flow network as a digraph $G$ with a ...
- 514