Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,513
questions
5
votes
1
answer
226
views
How can one construct a densest graph with no k-clique?
Given integers $k$ and $n$ with $2 \le k < n$,
how does one construct a graph on $n$ vertices
that contains no $k$-clique and has the maximal
number of edges?
This sounds like basic ...
- 13.4k
2
votes
1
answer
274
views
Number of Vertex Covers and Permanent
Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?
- 6,695
2
votes
2
answers
2k
views
polygonal triangulation and 3-colorability
Lets define polygonal triangulation a triangulation which has a hamiltonian cycle.
It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable....
- 43
7
votes
4
answers
1k
views
What are the best known upper bounds and lower bounds for computing O(log n)-Clique?
Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great
- 11.9k
1
vote
3
answers
5k
views
Is it possible to have a 4-coloring for a non-planar graph ? [closed]
I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable.
The question is ...
CommunityBot
- 1
7
votes
4
answers
903
views
A relaxed Steiner Tree Problem
Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices ...
- 294
23
votes
3
answers
2k
views
What bounds can be put on counting reachable nodes in a dag?
Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is ...
- 2,479
11
votes
1
answer
448
views
Computation of max H-free sets
In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
CommunityBot
- 1
17
votes
1
answer
598
views
Sensitivity of Graph Properties
In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...
- 3,372
19
votes
1
answer
1k
views
Construction of graphs where every pair of vertices have an unique common neighbor
Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
- 50.5k
2
votes
3
answers
1k
views
Best bounds for the longest path optimization problem in cubic Hamiltonian graph?
optimization problem
Input: cubic Hamiltonian graph
feasible solution: A simple path
measure to optimize: length of the simple path
Design a polynomial-time algorithm that outputs the longest path ...
- 50.5k
17
votes
1
answer
1k
views
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
...
- 11.4k
20
votes
2
answers
1k
views
Succinct circuit representation of graphs
The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:
END OF THE LINE: Given circuits S and P ...
- 50.5k