Tagged Questions
3
votes
0answers
37 views
Embeddings of graphs on surfaces
I need your help in the next problem:
I use $N_g$, $g \geq 1$, to denote the nonorientable surface which can
be constructed by inserting $n$ cross-caps on the sphere (these cannot be embedded in ...
1
vote
0answers
28 views
Topological graphs
Given the universel covering space $\hat{X}$ of $X$ by $p:\hat{X}\rightarrow X$, there exists a bijection between subgroups $H<G=\pi_1(X,x_0)$ and covering spaces $\tilde{X}\rightarrow X$ with ...
2
votes
0answers
21 views
defining relationship between geometric entities (features)
I have different features located on a plane (2D); I want to define this structure mathematically in a way to represent their relations. Some of features are aligned in horizontally, vertically or ...
2
votes
1answer
31 views
Isomorphic graphs + alpha
Which of the following graphs are isomorphic ?
I. 4 vertices A,B,C and D are positioned to form a square with side AD missing.
i.e, AB,BC and CD are the sides and they are perpendicular.
II. 4 ...
9
votes
2answers
120 views
Representation theorems for groups
There are two baffling representation theorems for groups:
Every group is isomorphic to the automorphism group of some graph. (see Frucht's theorem)
Every group is isomorphic to the fundamental ...
1
vote
2answers
54 views
Some questions on toroidal graphs
The complete graph $K_4$ is planar, and like every planar graph it is also embeddable into the torus.
a) Why does $K_4$ count as a triangulation of the sphere, but not of the torus?
b) What's the ...
3
votes
1answer
114 views
Let G be a bipartite graph all of whose vertices have the same degree d. Show that there are at least d distinct perfect matchings in G
Let G be a bipartite graph all of whose vertices have the same degree d. Show that
there are at least d distinct perfect matchings in G. (Two perfect matchings M1 and
M2 are distinct if M1 does not ...
4
votes
1answer
79 views
Action of a subgroup of finite index on a tree induced by an action of a group on a tree
Let $G$ be a group wich acts on a tree $\Gamma$. Then $U$ acts on $\Gamma$ for every $U\leq G$.
Question: Why does the following hold?
If $|G:U|<\infty$. Then the minimal $U$-invariant subtree ...
1
vote
1answer
81 views
What is difference between annulus (cylinder) and disk in graph routing?
What is difference between annulus (cylinder) and disk in graph routing?
I know annulus is disk with hole, or I can imagine how is similar to cylinder, but my problem is, I can't understand this ...
3
votes
0answers
49 views
topology on a graphs space
Let $\mathcal{G}$ be the set of locally finite, connected rooted graphs $(G,v)$ up to isomorphism $\cong$.
Denote by $[G,v]_r$ the sub-graph of $(G,v)$ induced by the vertices at distance $\leq r$ ...
1
vote
1answer
98 views
Is every planar graph without triangles 3-colorable?
In other words, can a planar graph without k3 have a chromatic number larger than 3?
3
votes
4answers
261 views
Can a graph be non 3-colourable without having k4 as a sub graph?
As the question asks, is it possible for a graph to have a chromatic number larger than three without it having a 4 vertice complete graph as a sub-graph?
4
votes
0answers
108 views
Tilings of the plane
There are many possible tilings (or tesselations) of the plane:
periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings)
aperiodic ones by a finite number of prototiles ...
1
vote
1answer
115 views
Graph Isomorphisms, Delaunay Triangulation on a sphere, and Kulikowski's Theorem
Suppose I have a collection of $n$ non-collinear points on a sphere, $\left\lbrace P_i\right\rbrace_{i=1}^n $. And I construct a mapping from this collection of points to the Delaunay Triangulation ...
3
votes
0answers
61 views
What is special about simplices, circles, paths and cubes?
There are some ubiquitous families of graphs — the complete graphs (or simplices) $K_n$, the circle graphs $C_n$, the path graphs $P_n$, and the hypercube graphs $Q_n$ — that intuitively ...
2
votes
1answer
59 views
Is there an unbiased random walk on a colored plane for any number of colors?
So I was trying to motivate the fundamental postulate of statistical mechanics (i.e. all microstates are assumed to be equally probable $-$ even if we can't practically measure them, but only their ...
9
votes
3answers
190 views
Etymology of “topological sorting”
This may be a dumb question, but what's "topological" about topological sorting in graph theory?
I thought topology was related to geometry and deformations.
1
vote
1answer
55 views
Follow-up: Topology on graphs
This is a follow-up to this question: In a graph, connectedness in graph sense and in topological sense
From Wikipedia
Graphs have path connected subsets, namely those subsets for which
every ...
4
votes
2answers
227 views
In a graph, connectedness in graph sense and in topological sense
From Wikipedia
Graphs have path connected subsets, namely those subsets for which
every pair of points has a path of edges joining them. But it is not
always possible to find a topology on the ...
0
votes
0answers
62 views
Topological Disconnected Graphs
How can I define a topology on a complete graph such that the connectedness of the subgraphs of it and the connectedness of the sets on the topological space become equivalent?
9
votes
2answers
272 views
“Planar” graphs on Möbius strips
Is there an easy way to tell if a graph can be embedded on a Möbius strip (with no edges crossing)?
A specific version of this: if a simple graph with an odd number of vertices has all vertices of ...
1
vote
2answers
88 views
How should I measure the total “closeness” of a finite number of elements?
Suppose I have n points and a way to measure the pairwise (probably non-Euclidean) distance between them. I would like to have some way to measure the total "closeness" of my points, but I'm not ...
4
votes
2answers
274 views
Closed curves on the discrete torus
I came about the following graph which seems to me the smallest discrete version of the torus:
Is this graph treated under a special name? What can be said about its cycles? Can its cycles be ...
3
votes
1answer
159 views
How many different four coloring exist for a given regular map?
Excluding maps that can be colored with 2 or 3 colors, how many different four coloring exist for a given regular map?
Naturally, two identical maps have to be regarded as differently colored if the ...
2
votes
1answer
456 views
Why is the Fundamental Group of a Connected Graph $G$ Free on elements in $G-T$; $T$ spanning tree for $G$)
The fundamental group $\Pi_1(G)$ of a connected graph $G$ is defined to consist of all loops
(i.e., closed paths) based at a given fixed basepoint/vertex $g \in G$ as elements,
and concatenation ...
6
votes
3answers
259 views
What sort of mathematical methods and models are used to model the brain
What sorts of mathematical tools, models and methods and theoretical frameworks do people use to simulate the function of the brain's neural networks? What mathematical properties do different brains ...
4
votes
3answers
202 views
When is a graph planar?
A graph G is planar if and only if xxx.
What can xxx be substituted for? Note that this is from a topological POV so a graph is a 1-dim cw complex and I guess the fundamental group should be used ...
