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

0
votes
3answers
73 views

Wolf cabbage and goat using dijkstra.

A farmer has to cross a river with a wolf, a goat and a cabbage. He has a boat, but in the boat he can take just one thing. He cannot let the goat alone with the wolf or the goat with the cabbage. ...
5
votes
1answer
195 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
4
votes
2answers
374 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
1
vote
1answer
58 views

Markov Chain with Memory

One of the defining characteristics of a Markov Chain is that it is memoryless: the next state depends only on the current state, and not on the set of preceding states. I'm looking for a ...
1
vote
0answers
23 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
0
votes
1answer
38 views

Defining a group from edge set of graph

I consider three islands represented by vertices V and the travel routes by ship are represented by the edges E. Here G=(V,E). I consider the non-empty set E and define the binary operation ...
1
vote
0answers
39 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
0
votes
0answers
19 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
0
votes
2answers
32 views

Upper and lower bound on graph

Find upper and lower bound for the size of a maximum (largest) independent set of vertices in an n-vertex connected graph, then draw three 8-vertex graphs, one that achieves the lower bound, one that ...
0
votes
1answer
37 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
2
votes
1answer
48 views

graph theory - why don't this graph exist?

Consider a tournament graph on $n$ nodes. Why does a graph with the following property not exist? Two nodes have the same outdegree and the other $n-2$ nodes have different outdegrees.
1
vote
1answer
25 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
6
votes
2answers
173 views

Knots and graphs

Every knot gives rise to a number of 4-regular planar graphs - by regular projections onto the plane - which just have to be enriched by an over/under flag for every vertex to be able to reconstruct ...
3
votes
2answers
87 views

Some kind of latin squares

Consider we have an $n\times n$ square. And for each element $a_{ij}$ there is a $L_{ij}$ set of permissible values(numbers) where $|L_{ij}| = n - 1$. Need to choose a value for each $a_{ij}$ element ...
2
votes
0answers
114 views

Almost regular graphs that are Hamiltonian

It is known that every $r$-regular graph on $2r+1$ vertices is Hamiltonian (Nash-Williams theorem, see here). Now, I wonder if there is a simpler way to show that the graph on $4n+3$ ($n \ge 1$) ...
0
votes
1answer
50 views

Find a subset of edges that lie on a simple path between two vertices

I am attempting to implement an algorithm found in a paper. One of the subtasks is: "given a directed acyclic graph $(V,E)$, subset of edges $E' \in E$, and vertices $u,v \in V$, find all edges $e \in ...
2
votes
0answers
38 views

Directed multigraph with numbered edges

Let we have a directed multigraph such that or every its vertex the set of edges from this vertex is finite and ordered (in other words, numbered $1,\dots,n$). I need this construct to describe ...
0
votes
0answers
29 views

Logic behind Force-directed graph drawing/layout

Here are the prerequisites for what I'm trying to do: I have n nodes (rectangles) in a 2D plane, that are evenly spaced (can have any x/y coordinates) Each node has width w and height h (each node ...
0
votes
0answers
12 views

Katz centrality and Node removal

I'm looking for any results about how Katz centrality changes when a given node is removed from a graph. For instance, if I define a function to be the average of the Katz centrality of the remaining ...
0
votes
1answer
43 views

Find if it is possible to draw a closed (cycle; not a path) continuous line…

... that crosses exactly once (only once) each interior line segment of the rectangle, whilst staying inside the rectangle for these 2 rectangles. My immediate reasoning was to remove all the outside ...
0
votes
0answers
36 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
2
votes
0answers
20 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
9
votes
1answer
273 views

What distinguishes topological spaces from graphs?

Topology would not "work" if one reverted the "direction" in the definition of continuous maps $f$: $$\text{open}(x) \rightarrow \text{open}(f(x))$$ It has to be $$\text{open}(f(x)) \rightarrow ...
1
vote
1answer
323 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
1
vote
2answers
401 views

Graph Theory: Tree has at least 2 vertices of degree 1

Prove that every nontrivial tree has at least 2 vertices of degree 1 by showing that the origin and terminus of a longest path in a nontrivial tree both have degree 1. Ok, so this statement is pretty ...
0
votes
2answers
69 views

Solving a graph [closed]

Prove or disprove: there exists a simple graph with 13 vertices, 31 edges, three 1-valent vertices, and seven 4-valent vertices. I need your help to solve this question.
4
votes
6answers
6k views

prove that a connected graph with $n$ vertices has at least $n-1$ edges

Show that every connected graph with $n$ vertices has at least $n − 1$ edges. How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges: a-----b-----c ...
2
votes
1answer
234 views

Why does my Barabasi Albert model implementation doesn't produce a scale free network

I'm trying to implement the Barabasi Albert model to generate some scale free network matching a power law distribution of degree. I'm using a value $m = 2$ for the main parameter of the algorithm, ...
0
votes
1answer
33 views

Is this a correct planar graph testing algorithm?

I want to know whether the below algorithm is correct for testing planr graph: step 1. Remove every degree-1 vertex and the edge that contains it. step 2. Remove every degree-2 vertex and replace ...
2
votes
0answers
39 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: $$\sum_{v ∈ V} deg(v) = ...
2
votes
1answer
73 views

Using a corollary of Tutte's theorem to prove a statement

I've been asked to prove that any graph $G$ which is $n$-connected, $n$-regular, and has even order has a one-factor. A hint that we were given for proving this was a corollary to Tutte's theorem, ...
0
votes
2answers
31 views

Minimum cut in a graph does not change when the weight of all edges is increased by one

Suppose we have a Graph $G$ in which weight of all edges is $> 1$ (positive). If we increase weight of all edges by one, why does the minimum cut $(S, T)$ of $G$ into two graphs remain the same? ...
0
votes
0answers
20 views

Geometric dual graph

It is well known the notion of geometric dual graph. Let $G^*$ be the geometric dual of a planar graph $G$. I need the proof that $(G^*)^* \cong G$ , where can I find it ?
0
votes
1answer
29 views

Graph homomorphism, and how to proof?

I want to know whether there exists a homomorphism from this graph (below in the image) to $K_5$ (complete graph with 5 vertices). If so, how can I prove this relationship? Since homomorphism is a ...
1
vote
1answer
35 views

can dijkstra's algorithm be applied as it is for undirected graph

I am wondering why can't Dijkstra's algorithm be applied as it is for undirected graphs. I mean instead of adding 2 directed edges to make it equivalent to a directed graph , why wouldn't it work if ...
7
votes
1answer
89 views

Graphs with uncountably many vertices

Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
6
votes
1answer
987 views

Proof Involving a Problem from “Good Will Hunting”

I don't know if any of you have seen the movie "Good Will Hunting" but there is a particular mathematics problem in the movie that is of interest to be. One of the problems used in the movie is "Draw ...
1
vote
4answers
48 views

Notation for two-vertex graph with m edges

Is there standard notation for the graph on two vertices with $m$ edges between them?
0
votes
1answer
37 views

Are minimum cut communities maximal?

I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al. Let $G(V, E)$ be some undirected weighted graph. Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum ...
0
votes
2answers
69 views

bipartite graph vs. directed acyclic graph

I'm having a hard time understanding the fundamental differences between a directed acyclic graph and a bipartite graph. Can anyone see how they are different from a mathematics perspective (or data ...
4
votes
1answer
256 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
0
votes
0answers
17 views

Complexity class of determining the gracefulness of an arbitrary graph G

Deciding if the a graph is a graceful one, is an NP problem. But my question ‎is "is there any proof that shows it is NP-Complete?" ‎ I've searched for the answer in many resources and papers, among ...
0
votes
2answers
43 views

The maximum no. of edges in a DISCONNECTED simple graph…

... on n vertices when it is not connected being equal to (1/2)(n - 1)(n - 2)... I can see that for n = 1 & n = 2 that the graphs have no edges... however I don't understand how to derive this ...
1
vote
1answer
25 views

Kirchoff Matrix -Tree Theorem

I'm reading a proof of the Kirchoff Matrix -Tree Theorem: If $G$ is a simple connected graph, $D$ the diagonal matrix with the vertices' degrees and $A$ the adjacency matrix, then in $M = -A+D$ ...
3
votes
1answer
364 views

Maximum cycle in a graph with a path of length $k$

I don't understand why this stands: Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Then $G$ contains a cycle ...
3
votes
1answer
230 views

Relation between articulation points and bridge edges

What is the relation ship between articulation points and bridges of a graph. Specifically, if there are no articulation points in a graph is it necessary that there will be no bridge edges.
0
votes
1answer
27 views

How to check if a 2D mesh is connected

I'm trying to optimize structures by using FEM and genetic algorithms (GA), the FEM solver is a commercial one, and I'm programming the GA. Something like this. My first approach is simple, just ...
4
votes
2answers
44 views

existence of K_3 in a graph with n^2+1 edges

I was working on this problem for quite a long time and was unable to solve it. Any help will be appreciated. Let $G$ be a graph with $2n$ vertices ($n \in \mathbb{N})$ and $n^2+1$ edges. Show that ...
1
vote
1answer
44 views

What's the 1-dimensional topology of a graph?

I'm reading through this paper here downloads.hindawi.com/journals/mpe/2013/815035.pdf where they say "Since a graph can be equipped with a topology to turn it into a a one-dimensional space, we can ...
3
votes
2answers
86 views

Properties of an element $x\in X$ in the Cayley-Graph $\Gamma(G,X)$ of a group G.

My problem is the following: Let $G$ be a group with generating set $X$. We can look the Cayley-Graph $\Gamma(G,X)$ of $G$. Let $x\in G$. Then it holds: $d_{\Gamma}(v,xv)\leq 1$ for all $v\in ...