Fdtxjr

Are ETF trackers fundamentally better than individual stocks?

Why Choose Less Effective Armour Types?

What's the meaning of “spike” in the context of “adrenaline spike”?

Are all passive ability checks floors for active ability checks?

Python if-else code style for reduced code for rounding floats

Who is flying the vertibirds?

My adviser wants to be the first author

What are substitutions for coconut in curry?

How to deal with taxi scam when on vacation?

Is it true that good novels will automatically sell themselves on Amazon (and so on) and there is no need for one to waste time promoting?

The hookrightarrow and its meaning

Did Ender ever learn that he killed Stilson and/or Bonzo?

Do I need to be arrogant to get ahead?

Brexit - No Deal Rejection

My Graph Theory Students

How do anti-virus programs start at Windows boot?

How to simplify this time periods definition interface?

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

Gantt Chart like rectangles with log scale

What should tie a collection of short-stories together?

How could a scammer know the apps on my phone / iTunes account?

Instead of Universal Basic Income, why not Universal Basic NEEDS?

Is it normal that my co-workers at a fitness company criticize my food choices?

It's a yearly task, alright

Describe all bipartite graphs modulo isomorphism with 12 vertices and each vertex of degree 3

5-vertex graphs with vertices of degree 2Finding all graphs with a certain vertex degree sequenceHow to induce maximum matching and minimum vertex cover from each other in a bipartite graph?How many four-vertex graphs are there up to isomorphism;Number of connected bipartite graphs with maximum possible degreeVertex degree and graph isomorphismDescribing a Bipartite Graph with unmatched verticesFind all non-isomorphic complete bipartite graphs with at most 7 vertices?Finding the number of unlabeled graphs with $n$ vertices such that each vertex has degree 2Find a largest graph with ten vertices, such that each vertex has even degree.

0

$begingroup$

Describe all bipartite graphs modulo isomorphism with 12 vertices and
each vertex of degree 3

Hi. I've been trying to figure what this question asks. Is this asking to draw and find out all graphs with 12vertices those are bipartite graphs and isomorphic among each other?
How is "modulo isomorphism" different from "isomorphism?

graph-theory

share|cite|improve this question

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

New contributor

Hannah Choi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax.
  $endgroup$
  – dantopa
  Mar 11 at 20:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It means, "Find a representative of each isomorphism class of the bipartite graphs with $12$ vertices such that each vertex is of degree 3." You can draw them, or describe them in words.
  $endgroup$
  – saulspatz
  Mar 11 at 20:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for your answer. Does this mean there will be certain number of these graphs that are isomorphic among bipartite graphs with 12vertices? Do I just need to graph 1 example ?
  $endgroup$
  – Hannah Choi
  Mar 11 at 20:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't really understand the first part of your question. Given any graph, there are infinitely many isomorphic copies of it. As to the second part, yes, you only need to show one example. The challenging part will be demonstrating that you have found them all. According to nauty there are $6.$
  $endgroup$
  – saulspatz
  Mar 11 at 20:46
  

  
  
  
  

add a comment | 

0

$begingroup$

Describe all bipartite graphs modulo isomorphism with 12 vertices and
each vertex of degree 3

Hi. I've been trying to figure what this question asks. Is this asking to draw and find out all graphs with 12vertices those are bipartite graphs and isomorphic among each other?
How is "modulo isomorphism" different from "isomorphism?

graph-theory

share|cite|improve this question

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

New contributor

Hannah Choi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax.
  $endgroup$
  – dantopa
  Mar 11 at 20:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It means, "Find a representative of each isomorphism class of the bipartite graphs with $12$ vertices such that each vertex is of degree 3." You can draw them, or describe them in words.
  $endgroup$
  – saulspatz
  Mar 11 at 20:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for your answer. Does this mean there will be certain number of these graphs that are isomorphic among bipartite graphs with 12vertices? Do I just need to graph 1 example ?
  $endgroup$
  – Hannah Choi
  Mar 11 at 20:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't really understand the first part of your question. Given any graph, there are infinitely many isomorphic copies of it. As to the second part, yes, you only need to show one example. The challenging part will be demonstrating that you have found them all. According to nauty there are $6.$
  $endgroup$
  – saulspatz
  Mar 11 at 20:46
  

  
  
  
  

add a comment | 

$begingroup$

Describe all bipartite graphs modulo isomorphism with 12 vertices and
each vertex of degree 3

Hi. I've been trying to figure what this question asks. Is this asking to draw and find out all graphs with 12vertices those are bipartite graphs and isomorphic among each other?
How is "modulo isomorphism" different from "isomorphism?

graph-theory

share|cite|improve this question

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

New contributor

Hannah Choi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

New contributor

Hannah Choi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

New contributor

Hannah Choi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

New contributor

Hannah Choi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked Mar 11 at 20:05

Hannah ChoiHannah Choi

1

1 Answer
1

active

oldest

votes

0

$begingroup$

I've been thinking about the question in your last comment, and I believe I understand it now.

This isn't a solution, but I don't think I can fit my response in a comment box. We have $12$ vertices of degree $3,$ so we know that the graph must have $18$ edges. Then there can be at most $6$ vertices in a bipartition set, since that will account for all $18$ edges. Therefore, both bipartition sets contain $6$ vertices. Call these sets $U$ and $V$.

The graph can be determined by its adjacency matrix. This is a $12times12$ symmetric matrix of $0$s and $1$s. If we list all the elements of $U$ before those of $V$ then the adjacency matrix takes the form $$beginbmatrix0&A\A^T&0endbmatrix$$ where 0 indicates a $6times6$ zero matrix and $A$ is $6times6$ matrix with three $0$s and three $1$s in each row and each column.

So, we can approach the problem by trying to determine all such matrices A. If you were to do it this way (and I'm not saying this is the best approach) then yes, you would no doubt generate many isomorphic graphs, and part of the problem would be to separate them into equivalence classes, and describe or draw one representative of each.

I don't know whaat the best way to approach this problem is. If you do use the approach alluded to above, be sure to apply as much symmetry as you can. For example, it's clear that the vertices can be numbered so that the first row of A is $[1 1 1 0 0 0]$ and the first column is $[1 1 1 0 0 0]^T.$

share|cite|improve this answer

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

Hannah Choi is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3144167%2fdescribe-all-bipartite-graphs-modulo-isomorphism-with-12-vertices-and-each-verte%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

I've been thinking about the question in your last comment, and I believe I understand it now.

This isn't a solution, but I don't think I can fit my response in a comment box. We have $12$ vertices of degree $3,$ so we know that the graph must have $18$ edges. Then there can be at most $6$ vertices in a bipartition set, since that will account for all $18$ edges. Therefore, both bipartition sets contain $6$ vertices. Call these sets $U$ and $V$.

The graph can be determined by its adjacency matrix. This is a $12times12$ symmetric matrix of $0$s and $1$s. If we list all the elements of $U$ before those of $V$ then the adjacency matrix takes the form $$beginbmatrix0&A\A^T&0endbmatrix$$ where 0 indicates a $6times6$ zero matrix and $A$ is $6times6$ matrix with three $0$s and three $1$s in each row and each column.

So, we can approach the problem by trying to determine all such matrices A. If you were to do it this way (and I'm not saying this is the best approach) then yes, you would no doubt generate many isomorphic graphs, and part of the problem would be to separate them into equivalence classes, and describe or draw one representative of each.

I don't know whaat the best way to approach this problem is. If you do use the approach alluded to above, be sure to apply as much symmetry as you can. For example, it's clear that the vertices can be numbered so that the first row of A is $[1 1 1 0 0 0]$ and the first column is $[1 1 1 0 0 0]^T.$

share|cite|improve this answer

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435

$endgroup$

add a comment | 

0

$begingroup$

I've been thinking about the question in your last comment, and I believe I understand it now.

This isn't a solution, but I don't think I can fit my response in a comment box. We have $12$ vertices of degree $3,$ so we know that the graph must have $18$ edges. Then there can be at most $6$ vertices in a bipartition set, since that will account for all $18$ edges. Therefore, both bipartition sets contain $6$ vertices. Call these sets $U$ and $V$.

The graph can be determined by its adjacency matrix. This is a $12times12$ symmetric matrix of $0$s and $1$s. If we list all the elements of $U$ before those of $V$ then the adjacency matrix takes the form $$beginbmatrix0&A\A^T&0endbmatrix$$ where 0 indicates a $6times6$ zero matrix and $A$ is $6times6$ matrix with three $0$s and three $1$s in each row and each column.

So, we can approach the problem by trying to determine all such matrices A. If you were to do it this way (and I'm not saying this is the best approach) then yes, you would no doubt generate many isomorphic graphs, and part of the problem would be to separate them into equivalence classes, and describe or draw one representative of each.

I don't know whaat the best way to approach this problem is. If you do use the approach alluded to above, be sure to apply as much symmetry as you can. For example, it's clear that the vertices can be numbered so that the first row of A is $[1 1 1 0 0 0]$ and the first column is $[1 1 1 0 0 0]^T.$

share|cite|improve this answer

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435

$endgroup$

add a comment | 

$begingroup$

I've been thinking about the question in your last comment, and I believe I understand it now.

This isn't a solution, but I don't think I can fit my response in a comment box. We have $12$ vertices of degree $3,$ so we know that the graph must have $18$ edges. Then there can be at most $6$ vertices in a bipartition set, since that will account for all $18$ edges. Therefore, both bipartition sets contain $6$ vertices. Call these sets $U$ and $V$.

The graph can be determined by its adjacency matrix. This is a $12times12$ symmetric matrix of $0$s and $1$s. If we list all the elements of $U$ before those of $V$ then the adjacency matrix takes the form $$beginbmatrix0&A\A^T&0endbmatrix$$ where 0 indicates a $6times6$ zero matrix and $A$ is $6times6$ matrix with three $0$s and three $1$s in each row and each column.

So, we can approach the problem by trying to determine all such matrices A. If you were to do it this way (and I'm not saying this is the best approach) then yes, you would no doubt generate many isomorphic graphs, and part of the problem would be to separate them into equivalence classes, and describe or draw one representative of each.

I don't know whaat the best way to approach this problem is. If you do use the approach alluded to above, be sure to apply as much symmetry as you can. For example, it's clear that the vertices can be numbered so that the first row of A is $[1 1 1 0 0 0]$ and the first column is $[1 1 1 0 0 0]^T.$

share|cite|improve this answer

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435

$endgroup$

share|cite|improve this answer

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435

answered Mar 11 at 22:46

saulspatzsaulspatz

17.3k31435