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 297
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
Does this graph exist?
What if you take $5$ paths with $k$ vertices each and glue them together at the endpoints? So $5(k-2)+2=5k-7$ vertices in all, and circumference $2(k-1)=2k-2$.
- 156k
11
votes
What is the cycle structure of a graph?
This is a vague question, but here is an attempt at an answer. Let $G$ be a graph, let $E$ be the set of edges of $G$, and let $C \subset 2^E$ be the set of cycles of $G$. Then knowing $C$ is equivale …
- 156k
3
votes
Accepted
Spanning trees of $H \cup e$ in terms of $H$
I get the following counterexample: Let $H$ be the graph on $12$ vertices, called $u_1$, $u_2$, ..., $u_{6}$, $v_1$, $v_2$, ..., $v_{6}$ with the following edges: $(u_i, u_j)$ and $(v_i, v_j)$ for all …
- 156k
10
votes
Accepted
Lower bound on # spanning trees in a connected graph
A quick google turns up:
Undirected simple connected graphs with minimum number of spanning trees by Zbigniew R. Bogdanowicz. According to this paper, the optimal graph is built as follows: Start wit …
- 156k
9
votes
Accepted
Where is it shown how to construct a decomposition tree for a series-parallel graph in linea...
It is easy enough to build the tree from a definition 2 description. Here is a sketch:
Suppose that SP graph $G$ occurs from subdividing graph $G'$ at an edge $e$, either in series or in parallel. Re …
- 156k
2
votes
Non-alternating chromatic factors?
Factor over what field?
Over $\mathbb{R}$, this is false. The roots of chromatic polynomials are dense in the complex plane, a result of Sokal. So, let $f(t)$ be a chromatic polynomial which has a ro …
- 156k
2
votes
3
votes
Why are Dynkin diagrams characterized by their eigenvalues?
The inner product which Ben describes (2-the adjacency matrix) also shows up in the classification of simple Lie groups/algebras. It is the matrix of inner products between the simple roots. For any n …
- 156k
8
votes
Complexity of determining if two graphs have same cycle matroid?
I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actu …
- 156k
3
votes
Accepted
Planarity of infinite graphs
This is a 1928 theorem of R. L. Moore "Concerning Triods in the Plane and the Junction Points of Plane Continua" PNAS Vol. 14, No. 1 (Jan. 15, 1928), pp. 85-88. Greg Kuperberg gave a nice proof of it …
- 156k
7
votes
Which paths in a graph are orthogonal to all cycles?
$\def\ZZ{\mathbb{Z}}$The answer to the boldfaced question is yes. Let $\Gamma$ be a connected graph with no cut edges. We will show that, if $\gamma \in C_1(\Gamma, \ZZ)$ with $\partial \gamma$ of the …
- 156k
7
votes
Accepted
Distinct closed walks with $2n$ steps in the $n$-dimensional hypercube
If you only wanted to quotient by symmetries of the cube, and not by shift (and presumably, reversal) of paths, there would be a very clean answer.
The symmetry group of the cube is $S_n \ltimes \{ \p …
- 156k
5
votes
Non-isomorphic matroids with the same Tutte Polynomial
Matroids of ranks $1$ and $2$ have simple descriptions, from which one can check that the Tutte polynomial determines the matroid in these cases.
A matroid of rank $1$ is always $\ell \geq 0$ loops t …
- 156k
3
votes
Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
There are silly examples. Consider the class "graphs that have a degree $1$ vertex". These can never have a Hamiltonian cycle, so the cycle problem is in $P$. If $G$ is $H$ with one extra vertex $u$ n …
- 156k
15
votes
Accepted
How can I prove that a particular family of graphs is integral?
$\def\CC{\mathbb{C}}$The specturm is integral.
The following trick is very useful in computing spectra of highly symmetric graphs. Let $G$ be a finite graph, let $\Gamma$ be a group of symmetries of …
- 156k