Toggle navigation
Mathematics
Vocabulary
Algorithms
trueshelf.org
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▲
date
0
Undergraduate
By
domotorp
on June 18, 2012 | Updated Jan. 16, 2017
Volley planning
Suppose there are n soldiers in a row who want to fire at the same time. Each of them has a constant memory and can only communicate with its neighbors, i.e. send message to left or right one and rece…
Puzzles
Puzzles
communication complexity
0
Undergraduate
By
TrueShelf Inc.
on Dec. 13, 2013 | Updated Jan. 16, 2017
Every edge in a triangle
For \(n \geq 3\), determine the minimum number of edges in a connected \(n\)-vertex graph in which every edge belongs to a triangle.
Mathematics
Graph Theory
triangles
0
Graduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Simplicial vertices in Chordal graphs
Let \(G(V,E)\) be a simple undirected graph. Let \(v \in V\) and let \(N(v)\) denote the neighbors of \(v\) in \(G\). The vertex \(v\) is said to be simplicial if \(N(v)\) induces a clique in \(G\). …
Mathematics
Graph Theory
chordal graph
0
Undergraduate
By
JeffE
on June 6, 2012 | Updated Jan. 16, 2017
Longest increasing digital subsequence
Let \(S[1..n]\) be a sequence of integers between \(0\) and \(9\). A digital subsequence of \(S\) is a sequence \(D[1..k]\) of integers such that each integer \(D[i]\) is the numerical value of a sub…
Computer Science
Algorithms
dynamic programming
0
Undergraduate
By
Shiva Kintali
on June 26, 2012 | Updated Jan. 16, 2017
Complete balanced binary trees are graceful
Label the vertices of a tree (with \(n\) vertices) with integers from \(1\) to \(n\). Now label each edge with the absolute difference of the labels of its incident vertices. The labeling is said to b…
Mathematics
Graph Theory
graph labeling
0
Undergraduate
By
Shiva Kintali
on June 25, 2012 | Updated Jan. 16, 2017
Separator number of a tree
Let \(T(V,E)\) be a tree with \(|V| = n\) vertices. Let \(W\) be a subset of \(V\). Prove that there is a vertex \(v \in V\) such that every component of \(T - v\) contains at most …
Computer Science
Mathematics
Algorithms
Graph Theory
trees
0
Undergraduate
By
TrueShelf Inc.
on Sept. 28, 2013 | Updated Jan. 16, 2017
Task assignment using Hall's Theorem
You are given a collection of tasks each of which must be assigned a time slot in the range {\(1,\dots,n\)}. Each task \(j\) has an associated interval \(I_j = [s_j,t_j]\) and the time slot assigned t…
Mathematics
Graph Theory
assignment
halls theorem
0
Undergraduate
By
Shiva Kintali
on May 31, 2013 | Updated Jan. 16, 2017
Characterizations of Eulerian graphs
It is well-known that a graph is Eulerian if and only if every vertex has even degree. Prove the following alternate characterization of Eulerian graphs Prove that if \(G\) is Eulerian and …
Mathematics
Graph Theory
eulerian graph
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Large min-degree implies perfect matching
Let \(G\) be a bipartite graph with partitions \(X\) and \(Y\) such that \(|X|=|Y|=n\). The degree of each vertex in \(G\) is at least \(n/2\). Prove that \(G\) has a perfect matching.
Mathematics
Graph Theory
matching
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Basics of Hamiltonicity
Let \(G(V,E)\) be a simple graph with \(n\) vertices and minimum degree \(\delta\). Also, for every two vertices \(x, y \in V\), \(|N(x) \cup N(y)| + \delta \ge n + 10\). Prove that \(G\) has a Hami…
Mathematics
Graph Theory
basics
hamiltonian cycle
1
2
3
...
24
25
26
next page »
icon
Sign In or Sign Up
icon
Invite Friends
×