Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,505
questions
9
votes
0
answers
288
views
Spectral gap for random bipartite regular graphs
For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where
$A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm ...
- 2,786
2
votes
3
answers
465
views
Graphs to download
Possible Duplicate:
Data for testing graph algorithms
I recently developed a parallel algorithm to solve the vertex cover problem.
now i need some graphs so i can test the speed of my algorithm ...
- 301
14
votes
1
answer
460
views
Hitting odd cycles
Is there anything known about the following problem?
Does it make sense at all?
What is it called?
Is it trivially equivalent to some other problem?
What is the time-complexity?
Given an undirected (...
- 1,296
1
vote
1
answer
290
views
Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs
Consider an unweighted undirected bi-connected planar graph.
Let $l_{v,u}$ be the length of the shortest path between nodes $v$ and $u$.
Let $l_{max}$ be the length of the longest shortest path ...
- 664
9
votes
2
answers
346
views
Are there any 'graphical' algebras that can describe the 'shape' of graphs?
One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a ...
- 303
5
votes
2
answers
3k
views
Making an adjacency matrix positive semidefinite
I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can ...
- 573
0
votes
1
answer
2k
views
vertex in a degeneracy ordering of a undirected graph
There is a step in Bron–Kerbosch algorithm
for each vertex v in a degeneracy ordering of G:
what is "a degeneracy ordering of G"? For example what is vertex in a degeneracy ordering in
this ...
- 109
2
votes
2
answers
576
views
General definitions for mixed graphs? (degrees, connectivity, etc)
I'm writing a framework for some graph theorical tasks and am unsure about some definitions regarding mixed graphs. Degrees and connectivity in particular.
A mixed graph G is a graph in which
...
- 123
7
votes
1
answer
176
views
Using MSOL for solving BIDS problem
From "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al) we know that any problem that can be written on MSOL (Monadic Second Order Logic) has a linear ...
- 531
4
votes
1
answer
525
views
Does this graph problem have a formal name?
Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through ...
- 141
19
votes
11
answers
1k
views
Models of random graphs, for real computer networks
I am interested in models of random graphs which are similar to the graphs of real computer networks. I am not sure if the common well-studied $G(n,p)$ model ($n$ vertices, each possible edge is ...
- 21.3k
10
votes
2
answers
2k
views
Maximizing sum edge weights
I am wondering if the following problem has a name, or any results related to it.
Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,...
- 9,850
11
votes
3
answers
1k
views
Regular Graphs and Isomorphism
I would like to ask whether there is an already published result on that:
We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and ...
- 573
15
votes
1
answer
853
views
Modular Decomposition and Clique-width
I am trying to understand some concepts about Modular decomposition and Clique-width graphs.
In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-...
- 531
1
vote
0
answers
139
views
Unit distance representation of a graph through Semidefinite Programming
I would like to ask on the number of different drawings of the unit distance representation of a graph, found through a semidefinite program (see www.cs.elte.hu/~lovasz/semidef.ps , p. 20-22). Since ...
- 573
4
votes
1
answer
249
views
How to determine if a labelled digraph contains a cycle with given labels?
Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at ...
- 141
1
vote
0
answers
283
views
Using Graphs/Graph Similarity as Features for a Learner
I'm working to construct a learner than can recognize whether two vertices in a property graph (digraph, vertices and edges can have arbitrary keys/values) modelling a social network in fact represent ...
- 111
13
votes
3
answers
653
views
The Dracula game
Background
This question is motivated by a board game called 'Dracula'. In this game there is one vampire and four hunters, the purpose of the hunters is to catch the vampire. The game takes place in ...
- 598
1
vote
1
answer
242
views
Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST
I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum ...
- 705
8
votes
2
answers
984
views
Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs?
I posted this on mathoverflow but with no luck:
Finding a connected 2-factor is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding two ...
- 20.7k
7
votes
2
answers
311
views
How hard is counting the number of vertex covers after a small perturbation?
Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G'=P(G)$. More precisely,...
- 6,665
15
votes
5
answers
889
views
References for Modular Decomposition
What are good papers/books to better understand the power of Modular Decomposition and its properties?
I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
- 1,733
13
votes
4
answers
832
views
What is the most important notion of sparsity for the design of efficient graph algorithms?
There are several competing notions of a "sparse graph". For instance, a surface-embeddable graph could be considered sparse. Or a graph with bounded edge density. Or a graph with high girth. A ...
- 1,952
5
votes
1
answer
282
views
Sending people to lunch together with minimal repetition
We have n people and split them up in groups of size x. Each group of x people goes to lunch together. Next time around when the groups are set up people who were in a group last time should not end ...
- 151
22
votes
5
answers
3k
views
Program for computing Tree decomposition of a graph
Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
user4654
7
votes
4
answers
1k
views
Approaching Number Theory conjectures through Graph Theory
i try to find if there was an attempt to prove any famous Number Theory conjectures like Goldbach conjecture or Twin Prime conjectures through Graph Theory.
I have in my mind something like the ...
10
votes
2
answers
397
views
Maximum imbalance in a graph?
Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average ...
- 319
2
votes
1
answer
333
views
Finding cycle with constraints
Given a graph in which each vertex $A_i$ has float value $B(i)$ between 0 and 1 inclusive.
How can we find a cycle (if such exists) with vertices $[C_1, C_2, ..., C_k]$ which violates following ...
user4543
5
votes
2
answers
750
views
Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
Let $G( n, m )$ be the set of all possible connected graphs of $n$ nodes and $m$ edges such that, for each $g_1 \in G( n, m )$, $g_2 \in G( n, m )$, if $g_1 \neq g_2$ then $g_1$ and $g_2$ are non-...
- 6,665
14
votes
0
answers
585
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,943
9
votes
1
answer
321
views
Bounding the number of edges between star graphs such that graph is planar
I have a graph $G$ which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let $H_1, H_2, \ldots, H_n$ be different star graphs of ...
- 705
0
votes
1
answer
196
views
Four color theorem and map pre-simplification of faces with less than 5 edges
It is already known that in searching for a solution of the four color problem, regular maps can be pre-simplified by removing all faces with less than four edges. This is described for example in the ...
- 179
4
votes
1
answer
172
views
Given a network flow, are there bounds on the change in weight on nodes?
Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight ...
- 319
5
votes
1
answer
295
views
Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?
Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?
For rectangular maps, for example, I intend maps that are made from overlapping ...
- 179
10
votes
1
answer
698
views
Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory
The post is related to:
https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles
How far away is the Lovasz bound from the zero-error ...
- 12.6k
38
votes
17
answers
5k
views
Conjectures implying Four Color Theorem
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-...
- 10.5k
5
votes
1
answer
234
views
Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints?
I have the following problem:
Given a set of path existence/absence constraints C (not necessarily for all pairs of vertices) and a (fixed) set of vertices V, generate a random DAG, s.t.
it is ...
- 664
10
votes
4
answers
748
views
What are the root difficulties in going from graphs to hypergraphs?
There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
- 6,960
1
vote
0
answers
220
views
constraints placement question
Suppose I have a set of squares. I get them in iterative way – one after another.
I would like to place the squares in some structure according to set of rules:
When a new square arrives all ...
- 189
7
votes
4
answers
1k
views
Trees: complexity of counting the number of vertex covers
Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
- 6,665
6
votes
3
answers
1k
views
Is there any good and free Introduction to topological graph theory
My knowledge in topological graph theory is in low, I need some good reference which has two simple thing, Definition of new concepts (like genus,graph embedding in surface, ...) also contains related ...
- 3,430
10
votes
1
answer
3k
views
Minimum path covering problem
We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the ...
- 101
5
votes
1
answer
611
views
Simple Constructions of Special Graph Families
Consider the following definition, taken from Chung's 1978 paper:
An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices,
$n \ge m$, having the property that, for ...
- 16.4k
8
votes
1
answer
964
views
Effect of different graph operations at algebraic connectivity of graph laplacian?
The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this ...
- 705
3
votes
2
answers
1k
views
Path of exact cost in edge labelled DAG?
Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels.
The problem is:
Find a path from $s$ to $t$ with cost $a$.
I suppose ...
- 223
4
votes
1
answer
1k
views
On Bipartite planar graph (again)
Given $n$ vertices of color $1$ and m vertices of color $2$, what is the maximal number of edges that can join them on the constraints - $(a)$ no edge joins has the same color ends and $(b)$ no two ...
- 12.6k
1
vote
1
answer
337
views
Number of Vertex Covers: when it is polynomial and when it is superpolynomial
The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to ...
- 6,665
5
votes
2
answers
478
views
Software for Graph Analysis
I have some graph-data which I would like to analyze. If the software could automatically determine some characteristics (Is the graph planar, clique number or any other graph property) it would be ...
- 605
2
votes
2
answers
260
views
Circle graph visualisation
I have a graph. I need visualise it with nodes arranged in a circle. How can I know whether it is possible arrange the nodes on a circle so that there no edges intersect in the visualised graph?
7
votes
1
answer
430
views
Combinatorial Independent set Algorithms for sub-classes of perfect graphs
As an extension to the question posed recently by Bulatov, I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent ...
- 348