3
$\begingroup$

I am thinking about flat knots and how they can represent graph. Most flat knots have a cord following an over-under pattern connecting back to itself. Here's a tripled up knot:

enter image description here

These sorts of knots must be quartic since all graphs with Eulerian circuits exist in even node connected graphs. Well, that and the fact any two cords crossing give four and only four edges.

Let $G$ be a connected, planar, quartic graph consisting of edges $E$ and nodes $V$.

Let $e_1, \dots, e_m$ be an Eulerian circuit of edges and $n_1,\dots, n_{m-1}$ be the corresponding nodes connecting consecutive edges. That is, $n_i$ connects edges $e_i$ and $e_{i+1}$. Additionally, let there be an $m$th node $n_m$ that connect $e_m$ and $e_1$.

My question is: Does there exist a map $f:V \to \{0, 1\}$ and an Eulerian circuit as specified above, such that $f(n_i)$ alternatives between $0$ and $1$? What are the necessary and sufficient conditions for a connected quartic graph for the above to hold?

$\endgroup$
6
  • $\begingroup$ Can you define what a flat knot and a quartic graph are? Also, in your Eulerian circuit, are you labeling some nodes twice? $\endgroup$
    – N. Owad
    Aug 29, 2016 at 15:49
  • $\begingroup$ A quartic graph is a graph where all nodes are order 4. The sequence of nodes may include duplicates. These are sequences, not enumerations. By flat knot, I mean what is written in the last paragraph. $\endgroup$
    – abnry
    Aug 29, 2016 at 15:52
  • $\begingroup$ All prime knots with at most 7 crossings are alternating knots, so to get a counterexample to your question (which I suspect exists), you want a good number of crossings. $\endgroup$
    – user98602
    Aug 29, 2016 at 15:58
  • $\begingroup$ Also, "most" knots are absolutely not alternating. Just the small ones. $\endgroup$
    – user98602
    Aug 29, 2016 at 16:48
  • $\begingroup$ I'm not talking about mathematical knots. I'm talking about decorative ones. Most of the decorative flat knots I see in books are alternating. $\endgroup$
    – abnry
    Aug 29, 2016 at 19:36

1 Answer 1

2
$\begingroup$

Let $G$ be a connected, planar, quartic graph and suppose we found a map $f$ and eulerian circuit as described in the question.

Since the degree of each vertex is four, then in the Eulerian circuit, each vertex $v$ must be included exactly twice in the sequence of nodes corresponding to the Eulerian circuit, say at index $i$ and $j$. Notice if the parity of $i$ and $j$ differ, then our map no longer has its alternating property (since $f(n_i) = f(n_j)$ and the difference between $i$ and $j$ is odd). Thus, it must be the case that the parity of $i$ and $j$ is the same and we can assign this parity to vertex $v$. If the parity is even, we'll say that $v$ is even-indexed, if it is odd, we'll say $v$ is odd-indexed.

This partitions the vertices of $G$ into even-indexed and odd-indexed vertices. Notice that due to the construction of Eulerian circuit, if we have an even number of vertices, then even-indexed vertices are only adjacent to odd-indexed vertices and odd-indexed vertices are only adjacent to even-indexed vertices and thus $G$ is in fact bipartite where each partition contains equal amounts of vertices (i.e. $G$ is a balanced bipartite graph).

If the number of vertices is odd, then we have something close to a bipartite graph with an added edge within one of the partitions. I would assume that you want you would want the alternating property of $f$ to also "loop back" in a sense though, i.e., $f(n_m) \neq f(n_1)$. This can only happen if the number of vertices is even, so we can throw out the case of an odd number of vertices if we want the alternating to loop back.

It's not too computationally taxing to determine if a graph is bipartite and to find the two partitions. If we are trying to find a Eulerian circuit and a mapping $f$ for $G$, we can simply test for bipartiteness and find the partitions. If the graph is not bipartite, we know that no circuit and mapping exist. If $G$ is bipartite, it suffices to pick any Eulerian circuit and map the vertices in one partition to $0$ and map the vertices in the other partition to $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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