2
$\begingroup$

I am interested in a certain class of graphs but have very little graph theory background, I was hoping that you guys could poke me in the right direction. The class of graphs is as follows:

  • Multi-graph
  • Connected components are directed Euler graphs
  • Minimal degree is $4$
  • Bipartite
  • We are given an embedding in $X$, a compact orientable surface of genus $g$.
  • The faces of the graph (when considering said embedding) are $4$-colourable.

I'm interested in any property of these graphs!

Thanks in advance!

  • 0
    If the graph isn't planar, then what do you mean by the dual graph?2012-03-06
  • 0
    Sorry, dual when it's given the embedding in the surface of genus $g$. I will fix this now.2012-03-06
  • 0
    Bump for information.2012-03-08
  • 0
    One last bump for info.2012-03-19
  • 0
    What does "directed Euler graph" mean? Does it mean that this graph is in fact a directed graph, and that it has a closed walk that uses each (directed) edge exactly once?2012-03-19
  • 0
    "A directed graph is Eulerian iff every graph vertex has equal indegree and outdegree." Or equivalently, if there exists a directed cycle using each edge once. (Directed Euler cycle)2012-03-20
  • 0
    Is the question too vague?2012-05-01
  • 0
    It's too off-the-wall. I don't even know if there are any such graphs - maybe the first thing to do is find a few of them and see what properties they have (in addition to the long list of properties defining them). There should be equations relating the numbers of vertices, edges, faces, and the genus.2012-05-01
  • 0
    The most basic example are the graphs with two vertices (v and u) and n>1 directed edges going from u to v and n directed edges v to u. They can be embedded in the sphere (think of sections of a orange) and they're clearly bipartite, they are actually 2-face colourable too (dual graph is just a cycle graph with 2n edges)2012-05-04
  • 0
    Also, my request was for these equations - I know very little graph theory sorry.2012-05-04
  • 1
    You might get better answers if you say why you became interested in this particular group of properties. Do these graphs arise in some problem you are trying to solve?2012-05-04

2 Answers 2