Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits

作者：Kijima Shuji; Tanigawa Shin ichi^*

来源：Discrete Mathematics, 2012, 312(16): 2466-2472.

DOI：10.1016/j.disc.2012.04.013

• Rigidity circuits
• Edge-disjoint Hamiltonian paths
• Medial graphs
• Sparsity
• Connectivity

A simple undirected graph G = (V, E) is a rigidity circuit if vertical bar E vertical bar = 2 vertical bar V vertical bar - 2 and vertical bar E-G[X]vertical bar %26lt;= 2 vertical bar X vertical bar - 3 for every X subset of V with 2 %26lt;= vertical bar X vertical bar %26lt;= vertical bar V vertical bar - 1, where E-G[X] denotes the set of edges connecting vertices in X. It is known that a rigidity circuit can be decomposed into two edge-disjoint spanning trees. Graver et al. (1993) [5] asked if any rigidity circuit with maximum degree 4 can be decomposed into two edge-disjoint Hamiltonian paths. This paper presents infinitely many counterexamples for the question. Counterexamples are constructed based on a new characterization of a 3-connected plane graph in terms of the sparsity of its medial graph and a sufficient condition for the connectivity of medial graphs.

• 出版日期2012-8-28