Your common factor graph

(10 pts)

In this assignment, you’re going to generate a graph from an ordered list of integers. If your list has n integers, then your graph will have n vertices named

Vertex i will be connected to vertex j iff the i^{\text{th}} and j^{\text{th}} integers in your list share a common divisor.

For example, if my list is 4,6,5,6, then my graph looks like so:

To get your list of integers, choose your name from the following list:

Once you have your list of integers, tell us the following:

1. What is your list?
2. What are the edges of your graph?
3. Give us a picture of your graph using Graphviz (see below).
4. What is the order (or number of vertices) of your graph?
5. What is the size (or number of edges) of your graph?
6. What is the degree sequence of your graph?
7. Does your graph have any cycles? If so, write one down.
8. Is your graph isomorphic to a complete graph? If not, tell us one feature that distinguishes your graph from an complete graph.

Graphviz??

There’s an awesome program called Graphviz that automates the process of drawing a graph with a reasonable layout. Graphviz is built in to our forum and can be accessed via bbcode. To generate the graph above, for example, I simply typed in the following:

[graphviz]
  graph{
    layout=fdp;
    0;1;2;3;
    0--1; 1--3; 3--0;
  }
[/graphviz]

Your graph will have 6 vertices so your code will look like so:

[graphviz]
  graph{
    layout=fdp;
    0;1;2;3;4;5
    # Put your edges here
  }
[/graphviz]

Graphviz is a wonderful piece of software with lots of options. In the examples here, we’ve specified the layout option, for example. Other choices for the value of layout include dot, circo, and neato. You can learn a lot more about Graphiz on it’s website, if you like.

My list is 12,11,9,12,2,9. The edges are:

0--2; 0--3; 0--4; 0--5; 2--3; 2--5; 3--4; 3--5

1. Integer list: 4, 4, 10, 8, 2, 5.
2. Edges:0--1;0--2;0--3;0--4;1--2;1--3;1--4;2--3;2--4;2--5;3--4
3. Visualization:

4. Order: 6
5. Size: 11
6. Degree sequence: (5,4,4,4,4,1)
7. My graph has no cycles since the edge of 2--5 would need to be traversed twice.
8. My graph is not isomorphic to a complete graph since node 5 throws off the balance by only being connected to node 2.

My list of integers:10, 10, 11, 8, 2, 4
Edges: 0--1; 0--3; 0--4; 0--5; 1--3; 1--4; 1--5; 3--4; 3--5; 4--5
Graph:

Order: 6

Size: 10

Degree Sequence: 4, 4, 4, 4, 0

Cycles: My graph does have a cycle in it without including node 2.
The cycle would be: 0--5, 5--3, 3--4, 4--1, 1--0, 0--4, 4--5, 5--1, 1--3, 3--0

Isomorphic: My graph is not isomorphic to a complete graph because node 2 is not connected to any other node on the graph.

1. Integer list: 4, 10, 6, 10, 11, 11.
2. Edges:0--1;0--2;0--3;1--2;1--3;2--3;4--5;
3. Visualization:

4. Order: 6
5. Size: 7
6. Degree sequence: (3,3,3,3,1,1)
7. My graph has one cycle, you can go from 0 all the way to 3 and back to 0.
8. My graph is not isomorphic to a complete graph since there are two nodes not connected to anything.

1. My list is: 8, 8, 9, 2, 3, 12
2. Edges: 0–1; 0–3; 0–5; 1–3; 1–5; 2–4; 2–5; 3–5; 4–5;
3. Visualization:

4. Order: 6
5. Size: 9
6. Degree Sequence: (5, 3, 3, 3, 2, 2)
7. My graph has several cycles within it, the largest would be [0–3–1–5–0]
8. My graph is not a complete graph since there are basically two groups formed, one with a factor of 2, another with a factor of 3, with the overlap being the number 12 which has 2 and 3 as factors. These two groups alone would each create a complete graph since all their individual components would share a factor, however my graph is like a combination of two complete graphs that meet at a single vertex.

1. My list is 4,4,8,4,8,10
2. 0–1; 0–2; 0–3; 0–4; 0–5;1–2; 1–3; 1–4; 1–5; 2–3; 2–4; 2–5; 3–4; 3–5; 4–5;

4. Order 6
5. Size 15
6. Degree sequence: (5,5,5,5,5,5)
7. My graph does have cycles, one of them being:
   0–1;1–2;2–3;3–4;4–5;5–0;
8. Yes it is isomorphic to a complete graph.

1. Integer list: 10,10,8,5,12,3
2. Edges: 0--1, 0--2, 0--3, 0--4, 1--2, 1--3, 1--4, 2--4
3. Visualization:

4. Order: 6
5. Size: 9
6. Degree Sequence: (4, 4, 4, 3, 2, 1)
7. My graph doesn’t have any cycles because 4–5 would have to be crossed more than once
8. No, my graph is not isomorphic to a complete graph since 5 is only connected to 4

1.) Integer List: 10, 12, 5, 9, 8, 8.
2.) Edges: 0-1, 0-2, 0-4, 1-3, 1-5, 4-5.
3.) Graph:

4.) Order: 6
5.) Size: 6
6.) Degree Sequence: 1, 1, 2, 2, 3, 3.
7.) The main cycle that can be seen in my graph would be 0-1-5-4 .
8.) My graph is non-isomorphic node 2 and node 3 are outliers.

1. Integers: 10, 9, 6, 12, 3, 5
2. Edges: 0–2; 0–3; 0–5; 1–2; 1–3; 1–4; 2–3; 2–4; 3–4; 5–0;
3. Picture:

4. Order (# of vertices): order 6
5. Size (# of edges): size 9
6. Degree Sequence: 3, 3, 4, 4, 3, 1
7. Any cycles? yes, 1–2–3–4–1
8. Isomorphic? it is not isomorphic because the last index (#5) is the only one that is sticking out from the other numbers.

@athach1 Shouldn’t 0–5 be an edge?