Use this tag for questions in graph theory. Here a graph is a collections of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
2
votes
1answer
968 views
How can I find the number of the shortest paths between two points on a 2D lattice grid?
How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this?
Eg. The shortest path between ...
1
vote
2answers
230 views
Returning Paths on Cubic Graphs Without Backtracking
I was once interested in the returning paths on cubic graphs . But I'm even more curious to have the number of ways without backtracking, which means doing one step forward and than one back (which ...
13
votes
7answers
1k views
What are good books to learn graph theory?
What are some of the best books on graph theory, particularly directed towards an upper division undergraduate student who has taken most the standard undergraduate courses? I'm learning graph theory ...
4
votes
4answers
1k views
3 Utilities | 3 Houses puzzle?
There's a puzzle where you have 3 houses and 3 utilities. You must draw lines so that each house is connected to all three utilities, but the lines cannot overlap. However, I'm fairly sure that the ...
3
votes
4answers
1k views
Given a simple graph and its complement, prove that either of them is always connected.
I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph.
Well, I always post my attempt at solution, but here I'm totally ...
0
votes
2answers
139 views
Help with graph induction question?
Given a graph $G$ with $n$ vertices, where $n$ is even, prove by induction that if every vertex has degree $n/2 + 1$, then $G$ must contain a 3-cycle. A 3-cycle is a set of 3 vertices, $a; b; c$ such ...
0
votes
1answer
256 views
Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems
Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. ...
0
votes
0answers
260 views
Directed graph, Max Flow, Dijkstra's algorithm [closed]
For directed graph ($G=(V, E)$,s,t,{Ce}) in which we want to maximize max flow.
All edge capacities are at least one. Define the capacity of an s-t path to be the smallest capacities of constituent ...
15
votes
2answers
713 views
Not lifting your pen on the $n\times n$ grid
The question I am asking has basically already been asked. Please see this MSE thread. There are a few questions brought up on that thread, and a smaller number were answered. The reason I am ...
9
votes
2answers
2k views
Understanding the properties and use of the Laplacian matrix (and its norm)
I am reading the wikipedia article on the Laplacian matrix:
http://en.wikipedia.org/wiki/Laplacian_matrix
I don't understand what is the particular use of it; having the diagonals as the degree and ...
5
votes
1answer
303 views
Rank of an interesting matrix
Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$.
$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
4
votes
1answer
296 views
eigen decomposition of an interesting matrix
Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$.
$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
4
votes
1answer
375 views
Sum of the shortest paths in graph
Let $ d_{G} \left(x,y \right) $ be the length of the shortest path between the vertices $x$ and $y$ in graph $G$ and let $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . ...
1
vote
1answer
183 views
Rank of a graph matrix
$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$.
There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
5
votes
1answer
187 views
Known bounds and values for Ramsey Numbers
Is there a good online reference that lists known bounds on Ramsey numbers (and is relatively up to date)? The wikipedia page only has numbers for $R_2(n,m)$.
I am specifically interested in known ...
