On Hamiltonian graphs arising from spatial orders of chromosomes of even number

• Autorzy: Dorninger D. , Hueber B.
• Języki publikacji: EN

Abstrakty

EN

According to Bennett's model of cytogenetics the spatial order in haploid chromosome complements is based on a similarity relation which gives rise to a multigraph G which is the edge-disjoint union of two of its subgraphs G1 and G2. For even chromosome numbers n Bennett's model postulates that the order of the n chromosomes is given by a Hamiltonian circuit of G alternating in the edges of G1 and G2 o However, such a Hamiltonian circuit does not always exist. We impose a weak condition on the similarity relation and prove that under this condition the assumed Hamiltonian circuit does exist for all even chromosome numbers n < 50, which settles the case for all biological relevant species with n pairs of chromosomes. Moreover we study the structure of the graph G in respect to cycle decompositions and possible generalizations of our results.

Słowa kluczowe

EN

Hamiltonian graphs; chromosomes

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2001
• Tom: Vol. 34, nr 3
• Strony: 733--742
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Dorninger D.

• Institute of Algebra and Computational Mathematics Vienna University of Technology Wiedner Haupstrabe 8-10 A-1040 Wien, Austria

autor

Hueber B.

• Institute of Algebra and Computational Mathematics Vienna University of Technology Wiedner Haupstrabe 8-10 A-1040 Wien, Austria

Bibliografia

• [1] M. D. Bennett, Nucleotypic basis of the spatial ordering of chromosomes in eucariotes and the implications of the order for genome and phenotypic variation, in: G.A. Dover and R.B. Flavell, eds., Genome Evolution. Academic Press, London, New York, 1982, 239-261.
• [2] J. S. Heslop-Harrison, M. D. Bennett, Prediction and analysis of spatial order in haploid chromosome complements, Proc. Roy. Soc. London Ser. B (1983), 211-223.
• [3] J. S. Heslop-Harrison, M. D. Bennett, The spatial order of chromosomes in root-tip metaphases of Aegilops umbellulata, Proc. Roy. Soc. London Ser. B (1983), 225-239.
• [4] D. Dorninger, On permutations of chromosomes, Contrib. to General Algebra 5 (1987), 95-103.
• [5] D. Dorninger, Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math. 50 (1994), 159-168.