ダウンロード数: 247
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.disc.2012.04.013.pdf | 119.25 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Kijima, Shuji | en |
dc.contributor.author | Tanigawa, Shin-ichi | en |
dc.contributor.alternative | 谷川, 眞一 | ja |
dc.date.accessioned | 2012-07-27T01:02:13Z | - |
dc.date.available | 2012-07-27T01:02:13Z | - |
dc.date.issued | 2012-08 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | http://hdl.handle.net/2433/158739 | - |
dc.description.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. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Elsevier B.V. | en |
dc.rights | © 2012 Elsevier B.V. | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.subject | Rigidity circuits | en |
dc.subject | Edge-disjoint Hamiltonian paths | en |
dc.subject | Medial graphs | en |
dc.subject | Sparsity | en |
dc.subject | Connectivity | en |
dc.title | Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.ncid | AA11525431 | - |
dc.identifier.jtitle | Discrete Mathematics | en |
dc.identifier.volume | 312 | - |
dc.identifier.issue | 16 | - |
dc.identifier.spage | 2466 | - |
dc.identifier.epage | 2472 | - |
dc.relation.doi | 10.1016/j.disc.2012.04.013 | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。