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

1

OP has clarified in the comments that some equations are wanted.

Assuming that the embedding in $X$ is a 2-cell embedding (that is, that each region is homeomorphic to a disk) we have Euler's formula, $$v-e+f=2-2g$$ where $v,e,f$ are the number of vertices, edges, and faces, respectively.

For any graph, $2e=\sum_x d(x)$, the sum over all vertices $x$ of the degree of $x$. Since the minimal degree is 4, we get $$e\ge2v$$

I think the 4-colorability gives another inequality relating these invariants, but I'm not remembering how to find it.

  • 0
    It is not necessarily connected - shouldn't it be $v - e + f = 1 - 2g + k$ where $k$ is the number of connected components? Also I would really appreciate it if you could post the $4$-colourability inequality. I've thinking of getting Topological graph theory by Tucker and Gross, is this a good idea?2012-05-13
  • 1
    How can it be an Euler graph, if it's not connected? You may find something of interest in http://web.science.mq.edu.au/~chris/topology/chap06.pdf2012-05-13
  • 0
    Doh! All connected components should be Euler graphs. Fixed question. Thanks for link - will read.2012-05-13
1

This is not a complete answer, but a sketchy response to one of Gerry Myerson's comments. Yes, infinitely many graphs satisfy the listed conditions.

Fisk and Mohar [JCTA 1994] proved that any undirected graph $G$ with the following properties is 4-colorable:

  • The shortest cycle in $G$ has length at least four.
  • $G$ can be embedded on a surface of genus $g$.
  • The shortest separating cycle in the embedding of $G$ has length at least $1000\,\log_2(g+1)$. A cycle is separating if it cuts the surface into two pieces. (The constant $1000$ is a conservative estimate; Fisk and Mohar prove the existence of an appropriate constant, but don't give any explicit value.)

It is fairly easy to construct arbitrarily large graphs $G$ that satisfy these requirements by subdividing any triangulation of the surface. The faces of the dual graph $G^*$ are 4-colorable (by definition of "dual"). Subdividing each edge of $G^*$ with a new vertex makes the dual graph bipartite. Finally, replacing each undirected edge with a pair of opposing directed edges makes the graph Eulerian with minimum degree $4$.