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 2672
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.
40
votes
7
answers
9k
views
Spectral graph theory: Interpretability of eigenvalues and -vectors
I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally di …
34
votes
3
answers
6k
views
Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers
Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], [3 …
22
votes
4
answers
3k
views
Can you determine whether a graph is the 1-skeleton of a polytope?
How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?
17
votes
3
answers
996
views
Primacy of arcs/arrows over vertices/objects
Freyd's Abelian Categories is the only textbook I know where the primacy of arrows over objects is taken seriously already in the axioms: there is no talk of objects at all. Only later one sees, that …
11
votes
6
answers
1k
views
Reasons for the importance of planarity and colorability?
Could it have been foreseen that - exemplarily - planarity and colorability would turn out to be such important concepts in graph theory (there's almost no textbook on graphs without two chapters devo …
10
votes
1
answer
1k
views
Reconstruction conjecture: Can other decks do the job?
The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs.
Question: Have other decks been investigated, finding out
that only vertex-delet …
10
votes
1
answer
897
views
Spanning polytopes
Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is Ham …
10
votes
5
answers
883
views
What's the name of graphs with each vertex contained in a cycle?
A tree is a graph with no vertex contained in a cycle.
A non-tree is a graph with some vertex contained in a cyle.
What's the name of graphs with each
vertex contained in a cycle?
9
votes
1
answer
911
views
An ubiquitous pattern of questions
There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):
Can a …
9
votes
3
answers
13k
views
Number of trees with n nodes and m leaves
Even searching for " 'number of trees' leaves " didn't reveal what I am looking for: an approach for calculating the (approximate) number of trees with exactly n nodes and m leaves. Any hints from MO? …
8
votes
7
answers
2k
views
Visualizing polyhedra from their 1-skeletons
Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton embedded in the plane, e.g. the hexahedral graph 5, as can be seen here.
Too …
8
votes
2
answers
2k
views
A weaker concept of graph homomorphism
In the category $\mathsf{Graph}$ of simple graphs with graph homomorphisms we'll find the following situation (the big circles indicating objects, labelled by the graphs they enclose, arrows indicatin …
8
votes
4
answers
870
views
Self-defining structures
The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed.
But consider derived rela …
7
votes
2
answers
1k
views
Yet another graph invariant: the similarity matrix
Preliminaries
Let $n \in \mathbb{N}$ and $v$ be a vertex of a graph $G$. Let the $n$-neighbourhood of $v$, $N_n(v)$, be the induced subgraph of $G$ containing $v$ and all vertices at most $n$ edges aw …
7
votes
1
answer
734
views
Complete tree invariants?
If we take a graph invariant to be "a property that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph" (from Wikipedia), I hav …