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

• Kijima, Shuji

• 谷川, 眞一

抄録

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.

収録刊行物

• Discrete Mathematics

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

  Elsevier B.V.

キーワード

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

詳細情報

• CRID: 1050845760667361024
• NII論文ID: 120004419119
• NII書誌ID: AA11525431
• ISSN: 0012365X
• DOI: 10.1016/j.disc.2012.04.013
• HANDLE: 2433/158739
• Web Site: https://api.elsevier.com/content/article/PII:S0012365X12001884?httpAccept=text/xml
• Web Site: https://api.elsevier.com/content/article/PII:S0012365X12001884?httpAccept=text/plain
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN