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 answers only
not deleted
user 9025
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.
0
votes
Enumerate spanning trees
Contract $e_1$ and delete $e_2$. Say $G$ is the original graph and $H$ is the new graph. Now run the tree enumeration algorithm on $H$. After reversing the contraction, you get all the spanning trees …
- 37.7k
5
votes
Existence of disjoint expanders in a graph
Yes, and you can find many more than $\log n$ of them.
Take an expander $G$ (for example a random cubic graph).
Take $k$ copies, where $k=o(n^{1/2})$. Now randomly
relabel each copy. The probability o …
- 37.7k
6
votes
What is graph canonisation?
Daniel's answer is imperfect in two respects. First, it defines a perfect hash function for graphs taking values in an arbitrary set, but a "canonical form" usually means more than that in the literat …
- 12.9k
2
votes
Enumerating all inequivalent planar embeddings of a planar graph
(Too long for a comment). Note that there are two different ways to define "all the embeddings" of a graph, both completely natural. I'll illustrate by example. Suppose a graph consists of two triangl …
- 37.7k
4
votes
Accepted
Generating 12-vertex plane graphs with 2 faces of degree 3 and all other faces of degree 4
The conditions "max face = 4, 21 edges, 12 vertices" characterize them. So:
plantri -pf4e21 12 -- 125 outputs (these are the 3-connected ones)
plantri -pf4e21c2 12 -- 120857 outputs (these are the 2- …
- 37.7k
6
votes
Accepted
Can we calculate the spectral radius of the universal cover for specific graphs?
For the complete graph minus an edge $K_n-e$, the spectral radius is the largest zero of
\begin{align*}&x^{14}+(30-10 n) x^{12}+(2 n^{3}+21 n^{2}-202 n +357) x^{10}\\
&+(-10 n^{4}+26 n^{3}+456 n^{2}-2 …
- 37.7k
6
votes
Accepted
Non-isomorphic walk-regular graphs with the same number of closed walks at any length
You are asking for two non-isomorphic cospectral walk-regular graphs, presumably not vertex-transitive.
The following two are examples. They are bipartite and 4-regular on 18 vertices. Both of them ha …
- 37.7k
5
votes
Accepted
Eulerian trails in complete graphs
In Ref 1 we called these things semi-Eulerian circular designs or semi-Eulerian quasigroups. They exist for all odd $n\ge 7$.
I'll state the problem again. Find an Eulerian circuit in $K_n$ which (co …
- 37.7k
3
votes
Accepted
Product decomposition for finite graphs
If I understand it correctly, there is a counterexample on page 1518 of this paper. Then again, I might not have read it carefully enough.
- 37.7k
6
votes
Accepted
Are "ultra-regular" bipartite graphs complete?
The complement of a matching generalises. Take $1<k<|X|$ and identify $Y$ with the $k$-subsets of $X$. Let $R(x)$ be the $k$-subsets containing $x$.
Note that the automorphism group acts as the symmet …
- 37.7k
0
votes
Graph vertices selection for paths sum minimalization
Your description is unclear, so I'm guessing a bit.
First, make a weighted complete graph $K$, where the weight of edge $ij$ is the distance in $G$ from $i$ to $j$.
Now you want a minimum weight perfe …
- 37.7k
10
votes
Accepted
Is there an algorithm to generate graphs with given order and diameter?
About 58% of the graphs on 12 vertices have diameter 3, so filtering a complete generation will be as fast as any. On 20 vertices the fraction has dropped to about 31% but the total is so vast that g …
- 37.7k
4
votes
Accepted
Determining graph Isomorphism: combining invariants
There will be strongly-regular graphs of the same parameters with equal values of all those invariants. Since the parameters determine the eigenvalues, all the invariants determined by the spectrum (s …
- 37.7k
3
votes
Accepted
Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every trian...
Gunnar Brinkmann informs me that this paper constructs planar triangulations where every hamiltonian cycle misses all the edges of many triangles. Some of the examples are even 5-connected.
- 37.7k
5
votes
Existence of certain regular graphs
All simple non-empty regular graphs of even degree have a two factor, see here . So you are just asking when they have a 1-factor. In addition to having an even number of vertices, the conditions are …
- 37.7k