# Questions tagged [graph-theory]

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

1,505 questions
Filter by
Sorted by
Tagged with
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
465 views

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
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
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
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
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
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
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
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
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
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
2k views

• 6,665
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