Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

3
votes
3answers
167 views

Looking for a particular generalization of the concept of a mathematical graph

I'm am trying to define a data structure to represent road networks. The immediately obvious structure is that of a graph - a set of nodes and edges that connect pairs of nodes. The nodes would ...
4
votes
2answers
3k 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
2answers
2k views

Graph Path Length Problem

Let $G$ be a graph such that $\delta(G) \geq k$. a) Prove that $G$ has a path of length at least $k$. solution: We know that $\delta(G) = \min\lbrace \deg(v) \mid v \in V(G) \rbrace$ if ...
4
votes
2answers
2k views

Degree Sequence of a Graph

I am trying to brush up my graph theory skills. I have not done any in over 4 years and i am rusty...If someone could help me out with this simple proof i would appreciate it. Prove that for any ...
1
vote
2answers
707 views

Distinct Hamiltonian cycles of the icosahedron and dodecahedron

I am seeking a listing of the distinct Hamiltonian cycles following the edges of the icosahedron and the dodecahedron. By distinct I mean they are not congruent by some symmetry of the icosahedron or ...
4
votes
2answers
361 views

Connected simple cubic graph

I am trying to understand this problem and yes this is from my assignment and I should be doing it myself, but I have been staring at it for 2 hours and not getting anywhere, so decided to post it ...
1
vote
1answer
166 views

In a graph, is it always possible to construct a set of cycle basis, with each and every edge Is shared by at most 2 cycle bases?

Let's say we have a graph, with a list of edges and vertexes (E,V), all the vertexes are connected to at least one edge at one end. There are many ways a complete ...
5
votes
2answers
328 views

Probability to find connected pixels

Say I have an image, with pixels that can be either $0$ or $1$. For simplicity, assume it's a $2D$ image (though I'd be interested in a $3D$ solution as well). A pixel has $8$ neighbors (if that's ...
9
votes
1answer
131 views

Increasing network throughput by cutting routes

Suppose we model traffic flow between two points with a directed graph. Each route has either a constant travel time or one that linearly increases with traffic. We assume that each driver wishes to ...