5
$\begingroup$

a) Given a set of positive integers, its common divisor graph (CD-graph) is the graph whose vertices are the integers, two of which are joined by an edge if (and only if) they have a common divisor greater than 1. Find a set of four positive integers whose CD-graph is the graph on the left below, and such that if the Collatz recipe (multiply by 3, and add 1 if odd; divide by 2 if even) is applied to each of the set's elements, the CD-graph of the new set of numbers is the graph on the right.

b) Are any two graphs on 4 vertices convertible one into the other in a similar way?

enter image description here

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
4
$\begingroup$

a)

My choice is: 3,9,110=2*55, 154=2*77. Here, 3 and 9 are connected, as are 110 and 154 as both have 11 as prime factor. These numbers are mapped to 10, 28, 77, 55. In this chain of numbers we have the connections 10-28-77-55-10, so we get the graph on the right.

b)

No, the graph with four vertices and no edges will be mapped onto a graph with at least three edges: at most one of the numbers of the first set can be even, so at least three of them are odd. After applying the Collatz map at least three numbers are even, and thus connected.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It would be interesting to know how many of the 121 pairs of graphs on 4 vertices are convertible. Almost all, surely. $\endgroup$
    – Bernardo Recamán Santos
    Commented Feb 21, 2020 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.