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
1k 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 ...
2
votes
2answers
243 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
153 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
397 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. ...
15
votes
2answers
716 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
305 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
298 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
379 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
185 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
191 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 ...
4
votes
2answers
151 views
Short proof for the non-Hamiltonicity of the Petersen Graph
It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either.
Is there a simple (short) argument that the ...
4
votes
2answers
197 views
How to find chromatic number of the hypercube $Q_n$?
How to find chromatic number the hypercube $Q_n$?
I know $\chi(Q_2)$=2 , $\chi(Q_3)$=2 , $\chi(Q_4)$=4
1
vote
1answer
152 views
Returning Paths on Cubic Graphs
Suppose we have a 3-edge-colorable cubic graph with $N$ vertices.
How many paths of length $N$ exist that return to its origin?
Or putting it differently: What is "Pólya's Random Walk Constant" on ...
1
vote
1answer
227 views
eigen decomposition of an interesting matrix (general case)
Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
0
votes
1answer
199 views
Calculating powers of 2 on a 2D grid without factoring.
Consider the following 2D infinitely large grid where the dots represent infinity:
...
21
votes
7answers
8k views
Online tool for making graphs (vertices and edges)?
Anyone know of an online tool available for making graphs (as in graph theory - consisting of edges and vertices)? I have about 36 vertices and even more edges that I wish to draw.
(why do I have so ...
14
votes
1answer
302 views
What are all conditions on a finite sequence $x_1,x_2,…,x_m$ such that it is the sequence of orders of elements of a group?
My Definition: The finite sequence $x_1,x_2,...,x_m$ of nonnegative integers, is said to be generated by the finite group $G$ iff
$n:=|G|=x_1+x_2+...+x_m$.
$n$ has $m$ divisors.
if ...
9
votes
2answers
279 views
How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?
How can I prove the identity
$$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$
I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
6
votes
3answers
504 views
Free Graph Theory Resources
What freely available graph theory resources are there on the web? In particular, I am interested in books and lecture notes containing topics such as trees, connectivity, planar graphs, the ...
6
votes
2answers
184 views
Lower bound on number of edges in “triangular” graph
Question I found in one of the previous year's exam:
Let $G$ a connected graph on $n \geq 3$ vertices, such that every edge participates in at least one triangle. Prove that $|E(G)| \geq ...
5
votes
2answers
531 views
connection between graphs and the eigenvectors of their matrix representation
I am trying to learn graph theory and the linear algebra used to analyse graphs. The texts I have read through have lots of lemmas and theorems proved. The proofs are convincing but I fail to see the ...
3
votes
1answer
337 views
Spanning Trees of the Complete Graph Avoiding a Given Tree
EDIT: I think everyone understood, but I never explicitly stated that I am looking at labeled spanning trees.
Let $T$ be a tree contained in $K_n$ (the complete graph on $n$ vertices). How can one ...
8
votes
1answer
132 views
Does there always exist such a convex hull?
Suppose that $v_{1}$, $v_{2}$, $\ldots$,, $v_{2k}$ are $2k$ points
in the plane. Is is true that there is always a convex hull of a subset
of the $2k$ points such that at least $k$ of the $2k$
points ...
6
votes
3answers
505 views
Is the empty graph connected?
Is the empty graph always connected ? I've looked through some sources (for example Diestels "Graph theory") and this special case seems to be ommited. What is the general opinion for this case ?
As ...
5
votes
2answers
266 views
How to determine if it's possible to draw a graph $G$ with a given set of vertices?
Given a list of vertices associated with its degree, says:
$$7, 7, 3, 3, 3, 3, 3, 1$$
Determine whether it is possible to draw a graph $G$, where $G$ is connected and un-directed.
Solution: ...
4
votes
1answer
1k views
planar graphs and vertices of degree 5
I am studying for my final exam and the prof suggested this problem.. so I'd really appreciate some help!! Thanks!
Let $G$ be non-null, simple and planar, with no vertex of degree less than or equal ...
4
votes
1answer
146 views
Fastest way to try all passwords
Suppose you have a computer with a password of length $k$ in an alphabet of $n$ letters.
You can write an arbitrarly long word and the computer will try all the subwords of $k$ consecutive letters. ...
3
votes
2answers
308 views
Proving component size based on number of edges and vertices.
I'm working on proving that if a simple graph with $n$ vertices has more than $5n^2/18$ edges then the graph has no connected component of size between $n/3$ and $2n/3$.
Logically, I think I could ...
3
votes
2answers
149 views
A less challenging trivia problem
There are 25 people sitting around a table and each person has two cards. One of the numbers 1,2,..., 25 is written on each card, and each number occurs on exactly two cards. At a signal, each person ...
3
votes
2answers
155 views
In a graph, the vertices can be partitioned $V=V_1\cup V_2$ so that at most half of all edges run within each part?
I am thinking of destroying all cycles of odd length by removing edges, so that I get a bipartite graph, with a partition $V_1$ and $V_2$ so that no edge in the new graph run within the two parts. ...
3
votes
1answer
675 views
How to prove that a simple graph having 11 or more vertices or its complement is not planar?
It is an exercise on a book again.If a simple graph G has 11 or more vertices,then either G or is complement $\bar { G } $ is not planar.
How to begin with this?Induction?
Thanks for your help!
3
votes
2answers
2k views
How to prove the optimal Towers of Hanoi strategy?
In the towers of Hanoi game, how do we know that we have the optimal algorithm for solving it? I thought about this and it seemed like any deviation from the standard strategies would be putting you ...
2
votes
1answer
210 views
Restricted read twice BDDs and context free grammars
Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1]
Quote:
Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled,
and a formal ...
1
vote
2answers
69 views
If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
Any help would be appreciated.
If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
1
vote
0answers
79 views
Shifted Young tableaux & Hook numbers & Bulgarian Solitaire
I would like to find articles or documentation regarding this process:
Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
1
vote
2answers
536 views
Showing that a graph has a cycle length less than something
I have the following exercise to do but don't know how to approach it:
Let $G$ be a graph with $n$ nodes ($n \ge 2$), and where every node has degree at least $3$. Show that $G$ has a cycle of length ...
-1
votes
0answers
393 views
Number of ways to construct a tree
Moderator's note: This is from an on-going contest http://ww2.codechef.com/MAY13/problems/TREE
The question will be unlocked in a week.
We have to construct a tree with $k \times n$ nodes ...
6
votes
1answer
307 views
How many weakly-connected digraphs of n vertices are there without loops and whose vertices all have indegree 1?
How many loop-free, weakly-connected digraphs of n vertices are there whose vertices all have indegree 1?
Here are two examples of such digraphs with $n = 5$:
$v_1 \to \{v_2, v_3, v_4, v_5\}; \; ...
6
votes
1answer
2k views
Number of simple paths between two vertices on an $n \times m$ square-grid graph?
I've encountered this whilst writing an optimisation benchmark for some heuristic search algorithms. Feels like there should be a basic solution out there!
A square-grid graph is constructed from $n ...
5
votes
1answer
233 views
What is the significance of the graph isomorphism problem?
It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
5
votes
2answers
667 views
How to construct a k-regular graph?
I have a hard time to find a way to construct a k-regular graph out of n vertices. There seems to be a lot of theoretical ...
5
votes
1answer
123 views
When does a biregular graph for the free product 2∗(2×2) have a 4 cycle?
I'd like to understand a graph theoretic property in terms of group theory. I have some boring graphs, and some neat graphs, all created from groups, but I don't know how to tell a boring group from ...
4
votes
1answer
105 views
Assigning alternate crossings to closed curves
This is a minor curiosity that I've been wondering about. Suppose that we draw a closed curve in the plane and that this curve intersects itself several times, but never twice in one spot. We can knot ...
4
votes
0answers
266 views
Bellman-Ford algorithm with changes
I got this question and I will be happy for a clue.
Here is a similar algorithm to the Bellman-Ford algorithm:
...
4
votes
1answer
361 views
Generating a Eulerian circuit of a complete graph with constant memory
(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices.
I would like to generate a Eulerian ...
3
votes
1answer
125 views
to check the minimal self-centered property of graphs
While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs.
My question is ...
