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 108884
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.
3
votes
1
answer
124
views
Is a simply connected locally 2-connected complex a union of spheres and planes?
Let $X$ be a (potentially infinite) 2-dimensional simplicial complex. Then each link at a vertex $x\in X$ is a graph.
Question. If $X$ is simply connected and each link is 2-connected (in the sense o …
- 13.6k
3
votes
0
answers
56
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of w …
- 13.6k
10
votes
2
answers
577
views
Is there a "simplest" way to embed a graph in 3-space?
I consider embeddings of graphs into 3-space with edges embedded as arbitrary curves. In the simplest (non-trivial) case the graph $G$ is a cycle or union of cycles, in which case the embeddings can a …
- 13.6k
10
votes
2
answers
219
views
Is the face lattice of the cube a polytope graph?
The face lattice of a
convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse dia …
- 13.6k
10
votes
3
answers
435
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ar …
- 13.6k
5
votes
1
answer
197
views
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3...
Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find
Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (where $G\ …
- 13.6k
5
votes
0
answers
81
views
When does the ΔY-family of a simple graph contain multigraphs?
Given a graph $G$, its ΔY-family is the smallest family of graphs that contains $G$ and is closed under ΔY- and YΔ-transformations.
Since YΔ-transformations can introduce multi-edges, the ΔY-family of …
- 13.6k
3
votes
1
answer
198
views
Are there many self-complementary perfect graphs?
A graph is perfect if it has no induced subgraph that is either an odd cycle (other than a triangle) or a complement thereof (note that the class of perfect graphs is closed under graph complement). A …
- 13.6k
4
votes
2
answers
249
views
Does the edge-graph of a centrally symmetric polytope determine which vertices are antipodal?
Given two origin symmetric convex polytopes $P_1$ and $P_2$ (that is $P_i=-P_i$) with the same edge-graph, but potentially of different dimensions and combinatorial types.
Let $\phi: G_{P_1}\to G_{P_2 …
- 13.6k
4
votes
0
answers
131
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory a …
- 13.6k
5
votes
0
answers
146
views
How to construct 4-regular graphs with few Hamiltonian decompositions?
A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is $2k$-regular.
Interest …
- 13.6k
10
votes
3
answers
497
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increase...
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$ …
- 13.6k
6
votes
1
answer
141
views
Embedding linklessly embeddable graphs without Borromean rings
A linklessly embeddable graph is a graph which can be embedded into $\Bbb R^3$ so that no two of its cycles are linked. For example, the Petersen graph is not such a graph.
Now, I can think of another …
- 13.6k
4
votes
2
answers
291
views
Can every involution of a symmetric directed graph be written as a power of another symmetry?
Let $D=(V,A)$ be a finite directed graph, and suppose that
$D$ is vertex-transitive,
$D$ is edge-transitive, and
between any two vertices there is at most one edge, in particular, if $(v,w)\in A$ the …
- 13.6k
2
votes
1
answer
94
views
Are zonotopes determined by their edge-graph?
General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And whe …
- 13.6k