Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options questions only
not deleted
user 22051
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an Eu …
- 4,713
3
votes
1
answer
2k
views
How random are random spanning trees?
Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices ap …
- 4,713
2
votes
1
answer
110
views
Completing a tree to a 2-connected outerplanar graph
Let $T$ be a given (finite) tree.
Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$?
Question 2: If the answer to Question #1 is negative, can …
- 7,226
11
votes
5
answers
2k
views
Are all almost regular graphs obvious?
Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate …
- 32.1k
0
votes
1
answer
324
views
Graphs with circulant distance matrices
The cycle has this property. For instance, the distance matrix for a 6-cycle is:
$A=\begin{bmatrix}
0 & 1 & 2 & 3 & 2 & 1 \\\\
1 & 0 & 1 & 2 & 3 & 2 \\\\
…
3
votes
1
answer
617
views
Toroidality testing
Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer-Myrvold planarity algorithm, which has a MATLAB and C++ implementation, and I would like to know if there …
- 1,161
4
votes
0
answers
242
views
Sets of spreads in graphs
Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices).
A partial $k$-resolution of $G$ is a set of pairwise …
- 6,962
8
votes
1
answer
335
views
Spectral lower bounds on the diameter of a graph
There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but …
- 570
7
votes
1
answer
506
views
Full-rank factorization of the graph Laplacian
Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and on …
- 570
9
votes
1
answer
414
views
Coherence between different ranking methods of a graph's vertices
Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a Perro …
- 30.1k
8
votes
1
answer
312
views
A conjecture about strongly regular graphs
Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$
So far I have …
- 6,962
5
votes
1
answer
282
views
Duration and critical groups order in sandpile models and chip firing games
The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least $d_{ …
- 24.2k
4
votes
1
answer
281
views
If a graph invariant is NP-Hard, is its "deck ratio" NP-Hard as well?
This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define $D_{\psi}(G …
CommunityBot
- 1
21
votes
1
answer
4k
views
What have simplicial complexes ever done for graph theory?
(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial comp …
- 24.7k
2
votes
2
answers
287
views
Which graphs generate a matroidal independence complex?
The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal independe …
- 14k