TY - JOUR
T1 - Sparsity and connectivity of medial graphs
T2 - Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits
AU - Kijima, Shuji
AU - Tanigawa, Shin Ichi
N1 - Funding Information:
We would like to thank Brigitte Servatius for her valuable comment. The first author is supported by Grants-in-Aid for Scientific Research . The second author is supported by Grant-in-Aid for JSPS Research Fellowships for Young Scientists and Kyoto University Start-Up Grant for Young Researchers .
PY - 2012/8/28
Y1 - 2012/8/28
N2 - A simple undirected graph G=(V,E) is a rigidity circuit if |E|=2|V|-2 and |E G[X]|≤2|X|-3 for every X⊂V with 2≤|X|≤|V|-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.
AB - A simple undirected graph G=(V,E) is a rigidity circuit if |E|=2|V|-2 and |E G[X]|≤2|X|-3 for every X⊂V with 2≤|X|≤|V|-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.
UR - http://www.scopus.com/inward/record.url?scp=84861867158&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861867158&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2012.04.013
DO - 10.1016/j.disc.2012.04.013
M3 - Article
AN - SCOPUS:84861867158
SN - 0012-365X
VL - 312
SP - 2466
EP - 2472
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 16
ER -