0
votes
1answer
14 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 ...
1
vote
0answers
25 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$ ...
0
votes
2answers
65 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 ...
0
votes
0answers
59 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.
1
vote
1answer
54 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 ...
3
votes
0answers
44 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 ...
1
vote
2answers
79 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 ...
1
vote
1answer
23 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?
3
votes
3answers
103 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 ...
2
votes
0answers
64 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 ...
6
votes
3answers
140 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 ...
4
votes
1answer
63 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 ...
1
vote
1answer
32 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 ...
1
vote
1answer
32 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 ...
0
votes
1answer
198 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 ...
12
votes
5answers
672 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 ...
13
votes
3answers
338 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, ...
5
votes
1answer
65 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; ...
7
votes
1answer
206 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 ...
5
votes
1answer
55 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 ...
4
votes
0answers
56 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
38 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
35 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
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 ...
11
votes
2answers
161 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
72 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
197 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 ...
5
votes
1answer
104 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
202 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
56 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
204 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
627 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
141 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
182 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 ...
5
votes
0answers
93 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
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 ...
10
votes
3answers
263 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
60 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
260 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
70 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?
13
votes
2answers
387 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
120 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
362 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
168 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
647 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 ...
7
votes
3answers
279 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
210 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 ...