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 algebraic-graph-theory
Search options not deleted
user 2233
Algebraic methods in Graph Theory; the linear algebra method, graph homomorphisms, group theoretic methods (for example Cayley graphs), and graph invariants. For graph eigenvalue problems use the spectral-graph-theory tag. For strongly regular graphs use the strongly-regular-graph tag. For Kneser graphs use the kneser-graph tag.
8
votes
Numerical invariants for a graph or its complement that are bounded by some constant
Let $c(G)$ be the number of connected components of $G$. Then for all graphs $G$,
$$
c(G)=1 \text{ or } c(\overline{G})=1.
$$
Here is a slightly more interesting family of examples. For a fixed in …
- 32.1k
5
votes
Characterizing graphs whose incidence matrix has the all ones vector in its row span
No, this is not true. Let $G$ be the bowtie graph (this is the graph obtained by gluing two triangles at a vertex $u$). Then, $G$ does not have a spanning regular subgraph, but $\mathbb{1}$ is in th …
- 32.1k
3
votes
Accepted
Do the cycles containing a fixed edge generate the cycle space of a graph?
For all $e \in E(G)$, $\mathcal{C}_e$ contains a basis of the cycle space.
Proof. Let $e=uv \in E(G)$, and let $C$ be a cycle of $G$. If $e \in E(C)$, then there is nothing to show. Thus, $e \noti …
- 32.1k
12
votes
Classes of graphs for which isospectrum implies isomorphism?
It is conjectured that almost all graphs are determined by their spectrum. It is funny that this conjecture fails spectacularly for many classes of graphs that one can think of. For example, almost …
- 32.1k