For questions about topological graph theory.

learn more… | top users | synonyms

0
votes
0answers
14 views

Can automorphisms of embedded graphs be extended to homeomorphisms of the surface they're on?

Let $G = (V,E)$ be a graph with an embedding $e$ on a surface $\Sigma$, and let $f$ be a graph automorphism of $G$. (Note: I am not sure of standard notation here. By $e$ I mean the map which ...
5
votes
2answers
180 views

Are resistor-battery networks always uniquely solvable?

Note: if you know the basics of circuits, feel free to skip the brief background; the question is at the bottom, starting below the triple horizontal rule. Most people with some physics background ...
1
vote
0answers
36 views

Can a planar graph have multiple edges joining 2 vertices?

If they are planar, do the properties $2E \geq 3F$ and $E \leq 3V-6$ remain true? For example, consider 2 vertices joined by 2 non-intersecting edges. Then $E=2, F=2$ and $V=2$ and $2E \not > 3F$. ...
0
votes
0answers
91 views

linearization topological sorting which repeatedly removes source nodes from the graph

The chapter suggests an alternative algorithm for linearization (topological sorting), which repeatedly removes source nodes from the graph (page 101). Show that this algorithm can be implemented in ...
1
vote
0answers
51 views

Prove that a finite complete graph can be embedded in $\mathbb{R}^3$

I've actually found a few intuitive examples where edges are taken to a twisted cubic and and the vertices are arranged in a certain way and that's very nice, but I'm actually more interested in a ...
0
votes
1answer
184 views

How many topological orderings exist for this graph?

Graph: 1 --> 4 2 --> 5 3 --> 6 My thoughts: There are 3 choices for the first slot. Then there are 3 choices for the second slot (Two remaining ...
1
vote
0answers
30 views

Embeddings and Covering faces?

I have a dude with the following problem. Suppose you have an 2-cell embedding of some simple graph $G$ on a orientable type surface $S_g$ (for example a plane graph), and you desire to find a set $A ...
3
votes
1answer
82 views

Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
1
vote
0answers
128 views

k6 embbeding on orientable surface of genus 3 with 6 pentagons faces

I need embbeding K6 on orientable surface of genus 3 . but I was asked to do it with the next stipulation : 5 faces only and all the faces in the embedding will be pentagons . In my opinion the way to ...
4
votes
0answers
62 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
1answer
120 views

2-cell embeddings of graphs in surfaces and Euler formula

I have a few questions regarding 2-cell embeddings of graphs in surfaces. Suppose $G$ is a 2-cell embedded graph in an orientable surface $S$, a) Is any connected subgraph of $G$ 2-cell embedded in ...
1
vote
0answers
48 views

Maximum minimum degree of a graph embedded on a surface

We shall consider only simple graphs. Let $G$ be a graph 2-cell embedded in a surface having Euler characteristic $\chi$. Let $\delta(G)$ be the minimum degree of $G$. Define $\delta_{\chi} = ...
2
votes
1answer
192 views

Drawing a graph on a torus

How do I approach this problem? For a drawing of a graph $G$ on a torus one defines a 'toric dual' $G^{t*}$ of $G$ in the natural way: every face of $G$ corresponds to a vertex of $G^{t*}$ and every ...
2
votes
1answer
126 views

planar graphs with minimum degree 4

Is it true: there is a simple planar graph $G$ with minimum degree $4$, each $2$ vertices of degree $4$ are nonadjacent $G$ has no vertices of degree $5$.
1
vote
2answers
98 views

Number of Vertices of Graphs

So, I was looking at some graph theoretical stuff, more specifically Topological Graph Theory, and I had a question about the definition of graphs: is there usually a condition in the definition ...
5
votes
2answers
103 views

Lower bounds on the number of edges in a nonplanar graph

Let $e$ be the number of edges and $v \geq 3$ the number of vertices in a graph $G$. We know that if $G$ is planar, then $e \leq 3v-6$. My question is the opposite. Is there some sort of inequality ...
1
vote
0answers
111 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
1answer
234 views

Do the terms “quiver” and “meta graph” refer to the same concept?

Do the terms "quiver" and "metagraph" refer to the same concept? Or is there a distinction I am missing. My sources are Quiver - http://ncatlab.org/nlab/show/quiver Metagraph - ...
1
vote
1answer
772 views

How to prove that a matrix is positive definite?

Let $L$ be a Laplacian matrix of a strong connected and balanced directed graph. Define $$ L^{s}=\frac{1}{2}\left( L+L^{T}\right) .$$ Let $D$ be a diagonal matrix with $$ D=\begin{bmatrix} d_{1} & ...
0
votes
1answer
200 views

What does face-width mean?

What is the meaning of the term face-width? I have seen the term used as a property of an embedding of a graph on a surface. I haven't found a definition.
2
votes
0answers
47 views

Is there a name for the number of edges that need to be removed to lower the genus of a graph?

The number of edges that need to be removed from a graph to disconnect it is called the edge-connectivity. Similarly, given a graph of genus $n>0$, there is a minimum number of edges that you have ...
3
votes
2answers
159 views

When is the dual graph simple?

This question is a follow-up and an improvement (I hope), to Is the dual graph simple? According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a ...
7
votes
3answers
133 views

graphs on surfaces

I'm looking for references on embedding graphs in surfaces (motivation: I was doodling and wondered how many distinct embeddings of $K_{3,3}$ into the torus there are.)