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.
1
vote
1answer
15 views
Prufer sequence for an order-2 tree?
All the algorithms for constructing a Prufer squence state that the input is a tree, but none give any output corresponding to an order-2 tree.
And Wikipedia gives this definition:" A Prüfer sequence ...
2
votes
1answer
23 views
number of paths between [i] and [j] on a directed unweighted cyclic graph?
Given a directed unweighted cyclic graph G consisting of up to 30 nodes and 30 edges find number of paths between i,j for all i,j in G
If there are infinite number of paths detect it
In ...
3
votes
1answer
31 views
Knight tour problem??
Consider an n × n chess board. For what values of n is it possible to find a knight’s tour around the
board which uses every possible move just once (in one direction or the other).
Here on what ...
2
votes
1answer
10 views
Is the expected number of components in a random graph $G(n,p)$ a decreasing function of $p$?
Let $X$ be the number of connected components in $G(n,p)$. If we fix $n$ and vary $p$, is $E(X)$ a decreasing function of $p$? I "feel" that this should be right because as $p$ increases there are ...
0
votes
2answers
18 views
Vertex between other vertices
I'm reading a paper on graph theory (On Disjoint Paths in Planar Graphs) and in an algorithm they define the set N to be the vertices between S1 and S2. But I'm wondering what exactly defines a ...
3
votes
1answer
40 views
$k$-partite spanning subgraph
I found an interesting problem:
Prove that for every $k>1$ any loopless undirected graph $G$ contains a $k$-partite spanning subgraph $H$ such that: $\left( 1-\frac{1}{k} \right)\deg_G(x) \le ...
0
votes
2answers
44 views
Create a Generating function
Let $P$ be the set of permutations all of whose cycles are of even length. Prove that the exponential generating function for $P$ is $\dfrac{1}{\sqrt{1-x^2}}$.
1
vote
0answers
29 views
Are Hamiltonian Paths still NP-Complete if you are allowed to revisit vertices?
If you have a one or more Hamilitonian cycles in a graph, but you remove the restriction of only being able to visit a vertex once, then is it still an NP-Complete problem?
That is, is there no ...
1
vote
0answers
33 views
Teleporting random walk
Given a directed graph $G = (V,E)$, to define a random walk on $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution (as mentioned in this paper)
I used a one ...
0
votes
0answers
28 views
Proof of Sperner's Lemma
I am looking for a concise and mathematically robust proof of the Sperner's Lemma.
The easiest proof I found so far is Math Pages Blog, but I don't get it without few details.
Following is the proof ...
4
votes
0answers
39 views
What can be said about the number of connected components of $G(n,p)$ random graphs?
By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$.
What can be said about the number of connected components? For ...
3
votes
1answer
18 views
Names and algorithms for subgraphs with smallest neighbourhoods
I'm curious about some terminology for graphs and the existence of an algorithm. Let $G$ be a graph and $H \leq G$ a subgraph. Is there a name given to $H$ if $|N(H)|$ is minimum over all subgraphs ...
0
votes
1answer
27 views
can plane graph be split?
When I consider a cycle graph (directed graph), I think the removal of some desired edges is logical.
But, If I refer that graph as a plane graph, that mean as a face
then Do the removal of some ...
0
votes
2answers
24 views
How can it be proved that each vertex can be at most in one strongly connected component in a directed graph?
How can it be proved that each vertex in a directed graph will exactly be in at most one strongly connected component? I do not see it in the graph below which I think contains a couple of connected ...
3
votes
1answer
22 views
Hypergraph Colorability
I'm interested in hypergraphs for which there are known (nontrivial) lower bounds on the chromatic number. If someone could point me to existing literature (survey papers etc) on this topic that would ...
