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 1266
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.
29
votes
The Matrix-Tree Theorem without the matrix
You can do without Cauchy-Binet.
If $e \in E(G)$, let $G/e$ denote the graph you get by contracting $e$ to a vertex. Let $t(G)$ denote the number of spanning trees in $G$. Then
$$
t(G) = t(G\setmin …
- 12.1k
27
votes
Accepted
Which graphs have incidence matrices of full rank?
The first answer identifies "incidence matrix" with "adjacency matrix". The latter is the
vertices-by-vertices matrix that Sciriha writes about. But the original question
appears to concern the inci …
- 12.1k
17
votes
Accepted
Are these three different notions of a graph Laplacian?
These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.
If t …
- 12.1k
14
votes
Spectral graph theory: Interpretability of eigenvalues and -vectors
If the graph has an eigenspace with dimension greater than one, then it is going
to be difficult to relate properties of eigenvectors to properties of the graph.
One way to get around this is to work …
- 12.1k
14
votes
Accepted
When the Lovász theta-function saturates its upper bound
Suppose $G$ is a $k$-regular graph on $n$ vertices, with least eigenvalue $\tau$.
Lovasz proved that
$$
\theta(G) \le \frac{n}{1-\frac{k}{\tau}}.
$$
Further if the automorphism group of $G$ acts …
- 12.1k
14
votes
code that produces all possible trees with n nodes.
In sage the command
list(graphs.trees(9))
produces a list of all trees on 9 vertices. As sage is open source, the code is available for inspection. The command
[tt.am() for tt in graphs.trees(9)] …
- 12.1k
14
votes
Accepted
Automorphism group of the cartesian product of two graphs.
All you need is in W. Imrich, S. Klavzar: "Product graphs: structure and recognition".
John Wiley & Sons, New York, USA, 2000. See also: Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. "Graphs an …
- 12.1k
12
votes
Accepted
Cayley graphs and its subgraphs
If $X$ is a vertex-transitive graph and the stabilizer of a vertex has order $m$, then the lexicographic product of $K_m$ by $X$ is a Cayley graph. We get the lexicographic product here by replacing e …
- 12.1k
12
votes
Endomorphisms and almost all graphs
The book "Graph Homomorphisms" contains an elegant proof that a random graph admits only the identity endomorphism.
The term to search on is "rigid graph". (This has two different meanings but they a …
- 12.1k
10
votes
Accepted
When Do a Few Eigenvectors of Graph Laplacians Not Determine the Graph?
The experimental evidence for adjacency matrices suggests that, for a random graph, its characteristic polynomial is irreducible over the rationals. I would expect that the characteristic polynomial …
- 12.1k
10
votes
Accepted
Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$
Hedrlín and Pultr proved that every monoid was the endomorphism monoid of a graph. See their paper "Symmetric relations (undirected graphs) with given semigroup" Monatsh. Math 69 (1965), eudml, DOI: 1 …
- 12.1k
10
votes
Accepted
When are the adjacency matrices of non-isomorphic graphs similar?
There is no characterization known of when a graph is determined by its spectrum. The probability that a tree on $n$ is determined by its characteristic polynomial goes to zero as $n$ tends to infinit …
- 12.1k
9
votes
Extended Hypercube Graph
The graphs you are considering are technically unions of classes in the binary Hamming scheme. The Hamming scheme is an instance of an association scheme, and it is studied at some length in the class …
- 12.1k
9
votes
Accepted
coincidence between minimal triangulation numbers and chromatic numbers
The answer to your "is it obvious" is "no". But it is a theorem in many cases. Wikipedia + one click takes to you "Solution of the Heawood map coloring problem" by Ringel and Youngs. There they comple …
- 12.1k
9
votes
Properties of Graphs with an eigenvalue of -1 (adjacency matrix)?
Despite a lot of effort, there's no interesting characterization of graphs with 0 as an eigenvalue. I do not think as much attention has been paid to $-1$, but I'd be surprised if anything useful cou …
- 12.1k