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.
2
votes
1
answer
294
views
Functions and graphs
Consider a finite set $X$ of order $n$ and a symmetric function $f: X \times X \rightarrow X$.
$f$ can straightforwardly be considered as a multidigraph with
$n$ "object" nodes, representing the …
- 9,720
3
votes
3
answers
778
views
Generalized degree spectrum
A standard graph invariant is the degree sequence, but it is well-known, that the degree sequence is not a complete graph invariant, i.e. a graph cannot be reconstructed uniquely from its degree seque …
- 9,720
2
votes
2
answers
268
views
Expressing a graph property with counting quantifiers
Assuming that one needs $k$ quantifiers to express that a graph contains an $k$-cycle, $\lfloor n/2 \rfloor$ counting quantifiers suffice to express that a graph is an $n$-cycle:
G has exactly $n$ no …
- 9,720
2
votes
2
answers
451
views
Almost or probably complete graph invariants?
Assuming that there are no known complete graph invariants in the spirit of Harrsion's question that do not depend on any labelling (see graph property at Wikipedia), I wonder if there are graph invar …
- 9,720
3
votes
2
answers
171
views
Faithfully embeddable graphs
Consider a weighted graph $G$ with weights $\omega_{ii}=0$, $\omega_{ij}=\omega_{ji}>0$, obeying the triangle inequality. One might want to ask into which metric spaces $X$ such a graph can be embedde …
- 9,720
5
votes
2
answers
574
views
Rado graph containing infinitely many isomorphic subgraphs
The Rado graph contains every finite graph as an induced subgraph. It surely contains some finite graphs infinitely often as an induced subgraph, e.g. $K_2$. Does it contain all finite graphs infinite …
- 9,720
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 …
- 9,720
1
vote
1
answer
1k
views
Complete vertex invariants
This question is related to Yet another graph invariant: the similarity matrix.
In graph theory there is much talk and research on graph invariants, especially complete graph invariants describing a …
- 9,720
4
votes
1
answer
1k
views
Smallest non-isomorphic strongly regular graphs
Motivation: I want to see how the 3-dimensional Weisfeiler-Lehman algorithm (see Logical complexity of graphs, p. 14) distinguishes between two non-isomorphic strongly regular graphs srg(v,k,λ,μ) in a …
- 9,720
3
votes
2
answers
1k
views
What is the cycle structure of a graph?
I have a vague imagination of what the cycle structure of a graph might be - something taking into account the numbers, lengths, Hamiltonianicities, Eulerianicities and whatsoever of cycles of a graph …
- 9,720
4
votes
1
answer
512
views
Generalized graph products in view of vertex-transitive graphs
The Cartesian product of two vertex-transitive graphs is vertex-transitive.
The Petersen graph is vertex-transitive but not the Cartesian product of two vertex-transitive graphs. But almost.
The Car …
- 9,720
1
vote
2
answers
206
views
Symmetry preserving graph products
Motivation
For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow …
- 9,720
4
votes
2
answers
206
views
Jordan-like cycles in graphs
[Added another complementary question below.]
Motivation
The 1-skeleton of the triangular bipyramid seems to be the smallest connected planar graph $G$ with the following
Property: There is a cycle $ …
- 9,720
0
votes
0
answers
188
views
Conjugate subgraphs and (maybe) a generalized Burnside's lemma?
It's rather straightforward, I guess, to define conjugate subgraphs of a graph via its conjugate nodes. (Two nodes $x,y$ are conjugate when there is an automorphism $g$ such that $x = g(y)$.)
Defi …
- 9,720
-1
votes
1
answer
148
views
Intersection graphs of 2-element subsets
I am interested in the intersection graphs of $\binom{X}{2}$, i.e. the set of all 2-element subsets of a (finite) set $X$.
[Motivation: One can represent every simple graph with $n$ vertices by an as …
- 9,720