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

1
vote
0answers
17 views

about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
1
vote
1answer
219 views

When counting faces in a planar graph - when is each edge counted twice?

So I'm confused even though this is supposed to be simple: From what I understand, in a planar graph, if we count the edges of each face, we should get $\sum F_t \le 2|E|$ because an edge can ...
0
votes
1answer
82 views

Counting nodes in a random tree

Suppose we have a random tree where the probability that a node has $n$ successors is given by $\delta(n)$. What is the distribution of the number of nodes at the $s$-th level deep in the tree, ...
14
votes
2answers
406 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
0
votes
1answer
53 views

Find Maximum-Matching in a tree $T(V, E)$ in $O(V)$

It's a question from a previous exam that I'm trying to solve with no success. Suggest a Dynamic-Programming algorithm for the following problem: Input: indirected tree $T(V, E)$. ...
2
votes
0answers
104 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
2
votes
1answer
172 views

Number of paths from A to B with no direction constraints

There's a fairly common problem finding paths which is usually stated something like this: Consider a grid that is 4 rows by 4 columns with the upper left corner named A and lower right corner ...
2
votes
2answers
73 views

How many spanning trees (undirected) are there with exactly k leaf?

It occurred to me that in order to find how many of those are there, for every $k$ it's a bit different way of thinking, for example: for $k$ = 3 the answer is: $\binom{n}{3}(n-3)\frac{(n-2)!}{2!}$ ...
0
votes
0answers
21 views

Induction over DAGs

I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid ...
0
votes
1answer
44 views

Is Wikipedia incorrect about Eulerian tour?

Wikipedia's Eulerian Path states, An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single ...
1
vote
1answer
44 views

How many connected and undirected graphs are there when d(v) = 2 for every vertex in the graph.

Well, at the beginning I thought the answer would be (n-1)! But it's not correct. My assumption to that answer was that its just like putting n people in a circle, but it doesnt seem like its exactly ...
3
votes
2answers
200 views

The problem of finding the shortest path/route/tour that visits every vertex at least once

I have a non-directed non-weighted graph and I want to find the shortest path/route/tour (I don't know which is the correct definition) that visits every vertex at least once. Is there an algorithm ...
17
votes
2answers
311 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
2
votes
1answer
49 views

Create a configuration - graph theory

I've encountered this (startling) difficult, to me, question: Create a configuration in the plane with a ring size 4, so that every internal vertex is of degree 5. Now, I assume I may not use ...
1
vote
0answers
92 views

What does “total variation on a graph” mean? How can I visualize it?

There is a paper " The Total Variation on Hypergraphs -Learning on Hypergraphs Revisited" which I am reading and I was not able to appreciate the term "total variation" in terms of graph theory. ...
0
votes
4answers
43 views

For trees with $10$ vertices, consider those which have a vertex of degree $8$. What is the number of such trees?

I'm trying to figure out what is the flaw in my thinking for this practice question. If a tree has $10$ vertices, one of which must have degree of $8$, this means that we essentially have a $K_{1,8}$ ...
1
vote
1answer
87 views

Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
3
votes
1answer
62 views

Is this perfect matching probability game really open?

A friend of mine heard from a friend of his of the following problem that my friend's friend claims remains open? The game is as follows: There are 100 persons with different names, their names are ...
1
vote
1answer
81 views

Prove the number of total dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another not so cute problem I made from a cute problem. Prove the number of total dominating sets of a bipartite graph is never exactly divisible by $2$ ( of the ...
2
votes
2answers
384 views

Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
0
votes
1answer
810 views

Find all “critical nodes” in a graph

Say there is a graph in which every node is connected to every other by some path. How would i find the particular nodes, which if removed would lead to some of the nodes NOT being connected to all ...
0
votes
1answer
102 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
1
vote
1answer
232 views

Maximum Flow - Ford Fulkerson

I tried using the Ford Fulkerson algorithm with the following question: The result I got was 25: I've been told that my solution is not correct. I was not told what the solution was however. ...
2
votes
1answer
269 views

Planar Graph & block

a) Show that a graph is planar if and only if each of its blocks (maximal 2-connected subgraphs) is planar. b) Deduce that a minimal nonplanar graph is a simple block.
3
votes
1answer
108 views

Problem in Chromatic Number

The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G). lemma : If G has a degree sequence $ (d_1, d_2, ... , d_v) $ with $ d_1 \ge d_2 \ge ...
2
votes
1answer
119 views

Chromatic Number

The smallest number of colors needed to color a graph $G$ is called its chromatic number, and is often denoted $\chi(G)$. Show that if graph $G$ is simple, then $$ \chi \ge \frac{V^2}{V^2 - 2E}. $$
4
votes
1answer
59 views

What is the Laplacian Matrix used for?

You can turn graphs into several matrix forms depending on what data you want to focus on. Does the Laplacian form have any uses on its own, or does it need to be paired with other things as some ...
4
votes
1answer
199 views

Graphs without nontrivial automorphism

I'm trying to solve two problems about graph automorphisms. I want to construct a bipartite graph without a nontrivial automorphism. I want to find the smallest possible number of nodes for a graph ...
4
votes
1answer
94 views

The number of dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another cute problem. Prove the number of dominating sets of a bipartite graph is never exactly divisible by $2$. A dominating set of a graph is a set of ...
0
votes
1answer
129 views

Minimum vertices set bipartite graph covering-special case

I was wondering if anyone here could give me any pointers as to how to solve the following problem. Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to ...
3
votes
0answers
131 views

Litterature on Dynamic graph theory

I was wondering if anyone knows any good articles or papers or books on graph theory that deals with changing graphs and not just static ones. So far I've only found qualitative descriptions of ...
1
vote
0answers
91 views

Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
0
votes
1answer
290 views

network structure — k-cliques vs p-cliques

In network structure, what is the difference between k-cliques and p-cliques, can anyone give a brief explaination with examples? Thanks in advanced! ============================ EDIT: I found an ...
1
vote
1answer
26 views

Name for the type of relation similar to the edge set of a regular directed graph?

For a binary relation over a set, if each member in the set appears the same number of times in the first position and in the second position in the relation, is there a name for such a relation? For ...
4
votes
2answers
82 views

What do they mean when they say “a blue $3$-regular subgraph”?

In page 4 of the following http://web.mat.bham.ac.uk/D.Kuehn/RamseyGreg.pdf the text says In any graph the number of vertices with odd degree must be even. For this reason there cannot exist a red ...
0
votes
1answer
79 views

Example of non-Abelianness of symmetric group for graphs

I know that for $n \ge 3$, $S_n$ is non-Abelian. I would like to work out an example in terms of graphs so to make it sure that I understand it right. A symmetric group of graphs of four vertices, ...
2
votes
1answer
205 views

Counting triplets with red edges in each pair

Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path ...
0
votes
1answer
320 views

Bipartite graph set cover

I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is an undirected bipartite graph G with the two vertex sets V1, V2. ...
1
vote
1answer
31 views

Random graphs question regarding exponents

On page 19 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf All in the first Paragraph. it gives an estimate of (they use equal instead of approximation) ...
0
votes
1answer
47 views

Order of deletion and contraction to form a minor

I have been reading a couple of sites regarding minors and have come across the statement that the order of deletion and contraction of edges do not matter. Why is that the case? In fact, I came up ...
0
votes
0answers
41 views

Graph theory problem of directed graph

Given a directed graph how can one find whether there exists a path that has all the vertices connected in short how can one know whether there exists a spanning tree in a directed graph or not. ...
0
votes
1answer
42 views

Find the number of vertices in the graph

Let $n\ge 1$ and $V_n = (\left\{ 1,2,...n \right\}\rightarrow\left\{ 0,1,2 \right\})$. Let us define $G_n = \left<V_n, E_n \right>$. $f,g$, are two vertices. They are connected iff: $$\left|\{ i ...
1
vote
2answers
180 views

Proving the theorem of graph theory

I want to know the proof of the condition of a Euler walk or tour in a directed graph. I googled a lot about it from MIT courseware to some other YouTube channels but I couldn't find any proof for ...
1
vote
1answer
162 views

If a k-regular graph is 1-factorable, then does it have chromatic index k?

Wikipedia says A k-regular graph is 1-factorable if it has chromatic index k. If I am correct, it means that if a k-regular graph has chromatic index k, then it is 1-factorable. Although it ...
4
votes
1answer
70 views

Error in my reasoning on $\dim_{VC}(H)=1\Rightarrow|H|\leq 1$?

Let $S$ be a set with $n$ elements. Let $P(S)=\{X\mid X\subseteq S\}$ Let $H\subseteq\mathcal{P}(S)$ (hypergraph with edge set $S$). Let $H_{|U}=\{U\cap A\mid A\in H\}$ Let ...
0
votes
1answer
42 views

Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
0
votes
1answer
66 views

3-color Graph colouring

Given a directed graph such that each node has indegree=outdegree=1 devise a algo that colour the graph such that no adjacent nodes has same color. **Note:**there is no self loop and graph has to be ...
0
votes
1answer
41 views

Identity in the 9 lectures in random graphs

In the 9 lecures in random graphs on pages 16/17 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf they say let $n_{0}(k)$ be the minimum $n$ for which $\binom{n}{k} ...
1
vote
0answers
681 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and ...
1
vote
0answers
134 views

Steiner tree problem in 3D?

Steiner tree problem in the plane (2D) is explained on wiki that though there's no straight solution, the solution has some properties, namely points added to the graph (Steiner points) must have a ...