Primitive rings and the full graph

A ring is primitive when the graph distance between every pair of its vertices equals the shorter distance along the ring. That is Franzblau’s shortest-path test. A chordless ring can fail it: the missing shortcut need not be an edge of the ring.

Distances, then the source

The search builds a ring from one source, the lowest-indexed member of that ring. Two facts have to hold at once.

Distances are taken on the whole graph. A shortcut may pass through a vertex whose index is below the source. Hiding that vertex makes the opposite vertex look farther away than it is, and a ring that is not primitive is kept.

After those distances are known, every vertex below the source loses its level. No path is extended through that vertex, so it is not written onto a ring this source emits. The ring is still reported once, from its lowest member.

Worked example

Number the vertices of a hexagon 1-2-3-4-5-6, and join a new vertex 0 to the opposite vertices 1 and 4.

A walk that refuses to enter vertex 0 reports distance 3 between 1 and 4. The hexagon then looks primitive, because each pair appears to sit at its ring distance.

The full graph has the path 1-0-4, so the distance is 2. The ring distance is 3, and the hexagon is not primitive. The two pentagons 0-1-2-3-4 and 0-1-6-5-4 are primitive. A chordless search keeps the hexagon as well, because no edge joins two non-consecutive vertices of the hexagon. The primitive search, and OVITO FindRings on this bond list, both reject the hexagon and keep the pentagons.

tests/test_ring_hop.cpp is that fixture. A depth-10 census is the primitive set. OVITO FindRings is a subset of it; the K2,3 counterexample is on Primitive rings and OVITO FindRings.

The shortest-path statement

Yuan and Cormack (Comput. Mater. Sci. 24, 343, 2002) build each ring from shortest paths. Let \(D\) be the largest size sought and write \(L = \lfloor D/2 \rfloor\). A ring of even size \(2L\) is a source plus two vertex-disjoint shortest paths to one vertex at level \(L\). A ring of odd size \(2L+1\) closes on an edge that joins two vertices both at level \(L\).

Franzblau’s filter then drops a candidate when any pair of its members is closer through the graph than along the ring. For a cycle \((v_0,\ldots,v_{n-1})\),

\[d_G(v_i, v_j) = \min_{k \in \mathbb{Z}} |i - j + kn|\]

must hold for every pair, with \(d_G\) the breadth-first distance on the whole neighbour graph. The search reports each ring once, from its lowest index, and sorts the list lexicographically. The output depends on the graph, not on the order of the rows.

The installed call is seams_rings_find in seams.h. The language ABI is seams_frame_rings. The CLI is seams rings.

The signatures are on C and C++.