For questions about topological graphs, flows, representation, planar, and book embeddings, geometric graphs, crossing numbers, coloring graphs, and other topics in topological graph theory.

learn more… | top users | synonyms

0
votes
0answers
26 views

Notion of degree for infinite graphs?

If you are studying graphs with vertices in the real numbers, you can define a notion of degree for a vertex as the length of the set of vertices directly connected to that vertex (if you wanted, you ...
1
vote
1answer
28 views

proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
0
votes
1answer
17 views

Can a chord determine two fundamental circuits in a graph

I was studying fundamental circuits,fundamental cutsets related theorems,then I came across a question in my mind: Is it possible that a chord with respect to a given spanning tree in a graph ...
3
votes
0answers
39 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
1
vote
1answer
33 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
0
votes
0answers
33 views

Graph theory and minor relation

I'm having some confusion with proposition $1.72$ of the Diestal book on Graph Theory which states that (ii) If $\Delta(X) \leq 3$, then every $MX$ contains $TX$ thus every minor with maximum degree ...
0
votes
1answer
24 views

Cloth cutting algorithm

I have a cloth in 3 dimensions represented as a triangle mesh, which is a kind of spatial graph. The nodes of each triangle are specified in a clockwise manner, such that I can consistently determine ...
0
votes
0answers
25 views

Topological minor and independence number

If $G$ and $X$ are graphs with $G=TX$, ($X$ is a topological minor of $G$) is there any sort of relation between $\alpha(G)$ and $\alpha(X)$ (the independence numbers of both). In addition if finding ...
0
votes
2answers
60 views

Examples of non-hamiltonian decomposable graphs

Good Afternoon! I read that Line graph of the Petersen graph is 4-regular 4-edge-connected and non-hamiltonian decomposable. Does someone knows examples (or references) of non-hamiltonian ...
0
votes
0answers
30 views

contraction and minors proof

I want to prove the following proposition $\textbf{proposition}$: $G$ is an $MX$ if and only if $X$ can be obtained from $G$ by a series of edge contractions, i.e if and only if there are graphs ...
0
votes
1answer
34 views

Question regarding normal spanning trees and a proof of existence

I'm reading about normal spanning trees in the Diestel book and i am somewhat confused by a number of things i'll try and work in chronological order. The first thing you need to know is about a tree ...
1
vote
0answers
11 views

difference between a combinatorial map and a rotation system?

Wikipedia has separate articles for combinatorial map and for rotation system, but as far as I can tell, their formal definitions are identical. Am I missing something? Or do these terms have ...
2
votes
0answers
50 views

Dessins d'Enfants and Real Algebraic Curves

I wrote a thesis on the Grothendieck theory of Dessins d'Enfants (after some articles by Leila Schneps). In Shafarevich, vol.2, there's a section on real algebraic curves. Is it possible to formulate ...
0
votes
0answers
83 views

The triangle inequality for shortest paths of graphs

In why-the-triangle-inequality I found the statement: for example if $d(a,b)$ measures the "length" of the "shortest path" between points $a$ and $b$ (and this can be interpreted quite ...
0
votes
0answers
38 views

An exercise of Diestel's book

Let $G$ be an infinite countable and connected graph that be not locally finite. By $\Omega(G)$, we mean the set of all ends of $G$. $\Omega(G)$ is compact if and only if for every finite set ...
1
vote
1answer
92 views

Finding the shortest and longest average path length in the set of all possible random graphs of a set size and set number of edges

In the set of all connected, undirected and simple graphes where the numbers of vertices and edges are known, what are the shortest and longest average path length (as defined here: ...
5
votes
2answers
326 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
39 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
361 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
56 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
533 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
33 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
93 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
206 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
69 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
151 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
53 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
287 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
148 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
117 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
116 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 ...
2
votes
0answers
128 views

Mathematical formulation of 'Indra's net' [closed]

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
311 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
1k 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
247 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
192 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
137 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.)