3
$\begingroup$
  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!

  • 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".2012-10-29
  • 0
    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.2012-10-29
  • 0
    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.2012-10-29
  • 0
    Thanks! What are the problems with the meaning of "translated"?2012-10-30
  • 0
    "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.2012-10-30

0 Answers 0