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

Access this Article

Search this Article

Abstract

A simple undirected graph G=(V, E) is a rigidity circuit if |E|=2|V|−2 and |EG[X]|≤2|X|−3 for every X⊂V with 2≤|X|≤|V|−1, where EG[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) 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.

Journal

  • Discrete Mathematics

    Discrete Mathematics 312(16), 2466-2472, 2012-08

    Elsevier B.V.

Codes

  • NII Article ID (NAID)
    120004419119
  • NII NACSIS-CAT ID (NCID)
    AA11525431
  • Text Lang
    ENG
  • Article Type
    journal article
  • ISSN
    0012-365X
  • Data Source
    IR 
Page Top