Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

Filter by
Sorted by
Tagged with
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 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 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
user avatar
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 ...
user avatar
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-...
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 ...
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 ...
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 ...
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-...
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 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 ...
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 ...
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

1
25 26
27
28 29
31