# Tagged Questions

27 views

### Is there a bound for the genus of the generalized petersen graphs?

I've looked online and could only find a bound for specific generalized petersen graphs. Does any bound (lower or upper) depending on $n$ and $k$, where $n$ is the order of a cycle and $k$ is the ...
102 views

### Difference between Topological Data Analysis and Graph Technology

I'm trying to understand the difference between Oracle's graph technology which apparently has an inherent understanding of topology and Ayasdi's Topological Data Analysis technology. Are these two ...
37 views

### Assigning manifolds to graphs in a functorial way

I am looking for ways to functorially assign manifolds (or more general topological spaces) to families of graphs. To be more precise, I am interested in functors from specific subcategories of the ...
52 views

### is a free group a discrete group?

Can I say that free groups are discrete groups? My question arises from the fact that free groups act on trees, and trees are graphs that can be viewed as a topological space (the graph topology).
22 views

### maximal independent set in a graph

Let $G$ be a graph and $A$ is a subset of vertex set of $G$. $A$ is said to be independent if for any $x, y \in A$, $(x,y) \notin E(G)$, i.e $x$ and $y$ not connected by an edge. Further A is said to ...
41 views

### Proof of Euler Characteristic for Sphere

Theorem 1. All cell decompositions of a sphere $S$ have Euler characteristic 2. This is well-known, but I had this idea for an intuitive proof: for any cell decomposition $\Gamma$ with $V$ ...
76 views

### Can you take off a sweater while wearing headphones?

This seems like a graph theory problem, but I'm not sure how to approach it. To clarify potential ambiguities, let's set up the situation. You are wearing a sweater (with one arm through each ...
65 views

### How I can prove euler characteristic of this complex is zero

$P$ is the poset of all nonempty subsets of $\{ 1, 2, 3, ....,n\}$ under set inclusion. Show that reduced euler characteristic of $\Delta P$ = $0$ I tried induction... but failed.
56 views

### Prove that two complex are isomorphic

Let $A:=$ matching complex of bipartite graph ($m \times n$ size) $B := m \times n$ chess board complex Show that $A$ and $B$ are isomorphic. I don't know exact definition of isomorphic... so i ...
46 views

### A stronger condition than planar graph?

Is there a name for this condition on a graph: a graph that can be embedded in the plane (planar), in such a way that of its univalent vertices do not lie inside any face? So, one can think of this ...
91 views

### How to detect whether the two graphs are topologically equivalent

From this link I construct a regular graph .How to construct a k-regular graph? here is the code https://github.com/xinyou/complexity/blob/master/graph/Graph.py 10-4 regular graph: here is one m ...
25 views

### Is there a proper name for a directed graph with one source and one destination?

The question says it all. Is there a name for a specific type of directed graph which contains only one source and one destination?
114 views

### Can every simple graph be embedded on a circuit board?

Here, a circuit board is defined as a pair of planar graphs with vertices identified, i.e. a ordered triple $\langle V,E_1,E_2\rangle$ such that there are planar embeddings $h_1,h_2$ for the planar ...
71 views

### How do you specify a link to a blind combinatorialist?

Regular projections of links look like graphs in the plane. So I'm wondering if it would be possible to specify a link up to isotopy with purely combinatorial data about this graph. If so, what kind ...
165 views

### How much topology for graph theory?

I am writing a thesis in the context of descriptive complexity in theoretical computer science and therefore need to study a little bit of graph theory. My background is not mathematics but computer ...
67 views

### Is a graph $G$ completely determined (up to labelling) by its spanning trees?

The title is essentially the question. I know that trees can be represented as a topology (equivalently a topological closure operator) on a set -- so I'm wondering if the collection of spanning trees ...
33 views

### Number of points that allow a topological space to stay connected

This question stems from a problem a friend of mine in the software field posed with regards to a graph. I am curious as to whether there is some analogue for topological spaces in general , maybe ...
38 views

### Contractibility of topological spaces associated to posets

Suppose $\mathcal{P}$ is a partially ordered set. To $\mathcal{P}$ we can associate a simplicial complex $K(\mathcal{P})$ whose $n$-simplices are the chains of length $n+1$ in $\mathcal{P}$. Since ...
206 views

### If we draw infinitely many lines on a table, can we find a triangle somewhere? [closed]

If we draw infinitely many lines on a table, can we find a triangle somewhere? We prove that there is a subgraph $C_3$ in $C_n$, which will be called a triangle. Suppose we have an infinite ...
1k views

### What's the relation between topology and graph theory

I read the Wikipedia articles for both topology, graph theory (plus topological graph theory). Does topology encompass also graph theory? Or topology is only about studying shapes while graph theory ...
347 views

### Metal Ball Cage Template Cardinality: A Brilliantly Lazy PROOF

N.B. - I'm looking for the simplest way to ascertain the number of templates $T$ (see below) comprising the structure from just one angle alone; that is, I'm sitting down looking up at this thing, ...
67 views

### Origin of the term “planar graph”

I would like to know who coined the term planar graph? I was able to trace the term back to a paper "Non-Separable and Planar Graphs" by Hassler Whitney, Proc. Natl. Acad. Sci USA. 1931 February; ...
254 views

### What distinguishes topological spaces from graphs?

Topology would not "work" if one reverted the "direction" in the definition of continuous maps $f$: $$\text{open}(x) \rightarrow \text{open}(f(x))$$ It has to be \text{open}(f(x)) \rightarrow ...
57 views

### The same destination regardless of origin

When I was very little, I didnâ€™t understand some basics of the space we live in. We always followed the same directions to get into town, to school, to the grocery store, and so on. So I figured that ...
61 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 ...
40 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 ...
38 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 ...
37 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 ...
166 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 ...
74 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 ...
207 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 ...
113 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 ...
262 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 ...
58 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$ ...
218 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?
723 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?
164 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 ...
200 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 ...
97 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 ...
65 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 ...
281 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.
67 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 ...
266 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 ...
71 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?
441 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 ...
129 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 ...
393 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 ...
171 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 ...
703 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 ...
282 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 ...