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.
  1. Let $L(G)$ be the line graph of a graph $G$. Is $G$ the line graph of $L(G)$?
  2. From the same article:

    Properties of a graph $G$ that depend only on adjacency between edges may be translated into equivalent properties in $L(G)$ that depend on adjacency between vertices.

    Are the followings also true?

    • Properties of $L(G)$ that depend only on adjacency between vertices may be translated into equivalent properties in $G$ that depend on adjacency between edges*.

    • properties of a graph $G$ that depend only on adjacency between vertices may be translated into equivalent properties in $L(G)$ that depend on adjacency between edges.

    • properties of a graph $L(G)$ that depend only on adjacency between edges may be translated into equivalent properties in $G$ that depend on adjacency between vertices.

  3. Let $D(H)$ be the dual graph of a planar graph $H$. Is $H$ the dual graph of $D(H)$?
  4. Are there results for dual graphs similar to part 2 for line graphs?

Thanks!

share|improve this question
1  
You can answer your first question by computing the line graph of a path on four vertices. As for (2), for the first bullet the answer is yes. The dual of the dual of a \emph{plane graph} is the original plane graph. I cannot make sense of (4) (for plane graphs the duality is between vertices and faces. I think technically the answer to (4) is "No". –  Chris Godsil Oct 29 '12 at 12:56
    
Thanks! For (1), the answer is no by your example. For other bullets in (2), are the answers no? For (3), I think the answer no, by an example of a square? For (4), I meant replacing edges by faces to make them make sense. –  Tim Oct 29 '12 at 13:01
    
In (2), for line graphs the answer to the first is yes and the answer to the following two is no. (There is some problems with the meaning of "translated".) For duals, the answers are yes, three times. –  Chris Godsil Oct 29 '12 at 13:42
    
Thanks! What are the problems with the meaning of "translated"? –  Tim Oct 30 '12 at 14:10
    
"Translated" is not a mathematical term. One underlying issue is that any two true logical statements are equivalent, and so one can be "translated" into the other. But the translation is probably not going to be very useful. –  Chris Godsil Oct 30 '12 at 19:31

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.