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
2answers
16 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
1
vote
0answers
11 views

Graphs: probability of two vertices, chosen at random, of being connected by a link

If I choose the vertices h and k in a graph uniformly, I know the probability of them being connected is $ \frac{2e}{n(n-1)} $ , where: e is the number of edges in the graph, n is the number of ...
3
votes
1answer
21 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
0
votes
1answer
25 views

Independent cycles in undirected graph

What is the algorithm that allows me to determine the independent cycles in an undirected graph. For example, in the figure below: The independent cycles: [2-12-4-5-13-2] [4-5-6-4] [4-10-11-7-6-4] ...
0
votes
2answers
16 views

Conflicting definition of eulerian graph and finite graph?

I'm reading Van Lint and Wilson: A Course in Combinatorics. There is one part of the book where he defines a finite graph: A graph is finite when both E(G) and V (G) are finite sets. Theorem ...
0
votes
1answer
19 views

Random walks on connected finite graphs

On a finite connected graph if a random walked is choosing the next vertex uniformly at random from among the edges of its current vertex, then it looks quite obvious to me that given an infinite walk ...
4
votes
0answers
62 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: ...
2
votes
1answer
41 views

How many ways are there to color the $H$-shaped tree with $3$ colors such that each color is used exactly twice?

How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red ...
1
vote
0answers
12 views

Kronecker product and the vec operator: confusion on proof of vec(AXB) = (transpose(B) ⊗ A) vec(X)

I was reading up on Kronecker products and vec operator from couple of sources and landed on the equation: vec(AXB) = (transpose(B) ⊗ A) vec(X) suppose ...
2
votes
1answer
38 views

Which are the natural morphisms between binary relations?

Which properties should morphisms $\alpha$ between binary relations have? $ (1) \qquad R \overset \alpha \longrightarrow R\,', \;R\subseteq X\times Y, \;R\,'\subseteq X'\times Y' $ Can those ...
5
votes
1answer
51 views

Proof that there is no closed knight tour on a $3\ \times\ 8$ - board

I want to prove that there is no closed knight tour on a $3\ \times\ 8$ - board by deleting $s$ vertices of the corresponding knight graph to get a graph with more than $s$ connected components ...
0
votes
0answers
16 views

Sparsification of a graph - with constraints

Say I have a graph (in matrix form) in which every vertex is connected to every vertex in some way. Instead of considering every connection, I would like to prune the graph such that it becomes more ...
0
votes
1answer
21 views

Maximal-size set of disjoint edges

Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)... Given an arbitrary (finite) undirected graph, I want to compute a ...
1
vote
1answer
19 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
3
votes
1answer
51 views

Details from a Proof that a Tournament has Property $S_k$

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.) Some technical details are omitted from a theorem in Alon and ...
1
vote
1answer
51 views

Determine cycle from adjacency matrix

Is there a way/algorithm to determine if there is a cycle in a graph if I only have the adjacency matrix and can not visualize the graph?
1
vote
0answers
22 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 ...
1
vote
0answers
38 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
18 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
27 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 ...
1
vote
1answer
21 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 ...
2
votes
1answer
47 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.
0
votes
1answer
34 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 ...
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
votes
1answer
17 views

Prove: let v be a vertex in a tree T. Then w(T-v) = d(v) [on hold]

w(T-v) means the component of T without(minus) v and d(v) means degree of v. it says that they are equal.
2
votes
0answers
31 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
24 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
10 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 ...
2
votes
0answers
19 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 ...
0
votes
0answers
26 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 ...
1
vote
2answers
54 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.
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
35 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) = ...
0
votes
2answers
29 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
14 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 ?
2
votes
1answer
70 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
1answer
28 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
31 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
82 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 ...
0
votes
1answer
41 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
2answers
40 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
4answers
41 views

Notation for two-vertex graph with m edges

Is there standard notation for the graph on two vertices with $m$ edges between them?
1
vote
1answer
21 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$ ...
0
votes
0answers
50 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
0
votes
1answer
35 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
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 ...
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 ...
3
votes
2answers
81 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 ...
0
votes
1answer
26 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
0
votes
1answer
26 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 ...