Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
If the graph isn't planar, then what do you mean by the dual graph? –  Gerry Myerson Mar 6 '12 at 22:38
    
Sorry, dual when it's given the embedding in the surface of genus $g$. I will fix this now. –  Alexander Mar 6 '12 at 22:43
    
Bump for information. –  Alexander Mar 8 '12 at 14:03
    
One last bump for info. –  Alexander Mar 19 '12 at 16:44
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? –  MJD May 4 '12 at 13:30
show 6 more comments

2 Answers

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.

share|improve this answer
    
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? –  Alexander May 13 '12 at 10:00
1  
How can it be an Euler graph, if it's not connected? You may find something of interest in web.science.mq.edu.au/~chris/topology/chap06.pdf –  Gerry Myerson May 13 '12 at 12:47
    
Doh! All connected components should be Euler graphs. Fixed question. Thanks for link - will read. –  Alexander May 13 '12 at 15:34
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.