Mixing
Given a graph G: how to find a formula to determine the number of squares in which a vertex participates?
$begingroup$
I should find a formula that, given a certain vertex v1 of a graph G, it returns the number of squares in which v1 participates.
I managed to find a solution for triangles, but in the case of squares, I am a having a hard time trying to figure out how to build a formula that distinguishes those walks that form a square starting at v1 and finishing at v1 from those walks that have length 4 and which do not form an actual square.
Any help would be greatly appreciated.
Thank you.-
graph-theory algebraic-graph-theory adjacency-matrix
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
$endgroup$
|
show 1 more comment
$begingroup$
I should find a formula that, given a certain vertex v1 of a graph G, it returns the number of squares in which v1 participates.
I managed to find a solution for triangles, but in the case of squares, I am a having a hard time trying to figure out how to build a formula that distinguishes those walks that form a square starting at v1 and finishing at v1 from those walks that have length 4 and which do not form an actual square.
Any help would be greatly appreciated.
Thank you.-
graph-theory algebraic-graph-theory adjacency-matrix
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
$endgroup$
3
$begingroup$
By a "square" you just mean a cycle of length $4$, don't you? Is the graph undirected? You want a formula in terms of what, the adjacency matrix of the graph? What is your formula for triangles?
$endgroup$
– bof
Jan 8 at 5:08
1
$begingroup$
Dear bof: sorry about the confusion. Yes, the graph is undirected. The formula should be in terms of the powers of the adjacency matrix. For example, for triangles, I should take the values of each vertex on the diagonal of A^3 and divide them by 2. Those would be the paths of length 3 that begin and end and each vertex. Therefore, they are triangles (I am discarding the counting on both directions by dividing the number by 2).
$endgroup$
– cadmus1324
Jan 8 at 16:27
$begingroup$
What are the different types of walks of length 4 that start and end at the same vertex? Can you think of a way to eliminate the ones you don't want?
$endgroup$
– Morgan Rodgers
Jan 9 at 20:27
$begingroup$
Dear Morgan, that's actually the main problem I can't solve: how to discard the 4-length walks that begin and end at v1 and which are not squares. For example, given the adjacency matrix A = [0110;1001;1001;0110] then A^4 = [8008; 0880; 0880;8008]. The conclusion should be that there is only one square in which v1 participates (in this particular case, v1 could be any vertex of G). Nevertheless, it is not clear to me how to formally discard the other 7 walks that are of length 4, but are not squares. Any help would be appreciated since I am clueless.
$endgroup$
– cadmus1324
Jan 10 at 2:22
$begingroup$
Anyone? I would greatly appreciate any help on this matter :(
$endgroup$
– cadmus1324
Jan 11 at 3:28
|
show 1 more comment
$begingroup$
I should find a formula that, given a certain vertex v1 of a graph G, it returns the number of squares in which v1 participates.
I managed to find a solution for triangles, but in the case of squares, I am a having a hard time trying to figure out how to build a formula that distinguishes those walks that form a square starting at v1 and finishing at v1 from those walks that have length 4 and which do not form an actual square.
Any help would be greatly appreciated.
Thank you.-
graph-theory algebraic-graph-theory adjacency-matrix
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
$endgroup$
I should find a formula that, given a certain vertex v1 of a graph G, it returns the number of squares in which v1 participates.
I managed to find a solution for triangles, but in the case of squares, I am a having a hard time trying to figure out how to build a formula that distinguishes those walks that form a square starting at v1 and finishing at v1 from those walks that have length 4 and which do not form an actual square.
Any help would be greatly appreciated.
Thank you.-
graph-theory algebraic-graph-theory adjacency-matrix
graph-theory algebraic-graph-theory adjacency-matrix
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
edited Jan 9 at 20:17
Alex Ravsky
40.4k32282
40.4k32282
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
asked Jan 8 at 5:04
cadmus1324cadmus1324
61
61
3
$begingroup$
By a "square" you just mean a cycle of length $4$, don't you? Is the graph undirected? You want a formula in terms of what, the adjacency matrix of the graph? What is your formula for triangles?
$endgroup$
– bof
Jan 8 at 5:08
1
$begingroup$
Dear bof: sorry about the confusion. Yes, the graph is undirected. The formula should be in terms of the powers of the adjacency matrix. For example, for triangles, I should take the values of each vertex on the diagonal of A^3 and divide them by 2. Those would be the paths of length 3 that begin and end and each vertex. Therefore, they are triangles (I am discarding the counting on both directions by dividing the number by 2).
$endgroup$
– cadmus1324
Jan 8 at 16:27
$begingroup$
What are the different types of walks of length 4 that start and end at the same vertex? Can you think of a way to eliminate the ones you don't want?
$endgroup$
– Morgan Rodgers
Jan 9 at 20:27
$begingroup$
Dear Morgan, that's actually the main problem I can't solve: how to discard the 4-length walks that begin and end at v1 and which are not squares. For example, given the adjacency matrix A = [0110;1001;1001;0110] then A^4 = [8008; 0880; 0880;8008]. The conclusion should be that there is only one square in which v1 participates (in this particular case, v1 could be any vertex of G). Nevertheless, it is not clear to me how to formally discard the other 7 walks that are of length 4, but are not squares. Any help would be appreciated since I am clueless.
$endgroup$
– cadmus1324
Jan 10 at 2:22
$begingroup$
Anyone? I would greatly appreciate any help on this matter :(
$endgroup$
– cadmus1324
Jan 11 at 3:28
|
show 1 more comment
3
$begingroup$
By a "square" you just mean a cycle of length $4$, don't you? Is the graph undirected? You want a formula in terms of what, the adjacency matrix of the graph? What is your formula for triangles?
$endgroup$
– bof
Jan 8 at 5:08
1
$begingroup$
Dear bof: sorry about the confusion. Yes, the graph is undirected. The formula should be in terms of the powers of the adjacency matrix. For example, for triangles, I should take the values of each vertex on the diagonal of A^3 and divide them by 2. Those would be the paths of length 3 that begin and end and each vertex. Therefore, they are triangles (I am discarding the counting on both directions by dividing the number by 2).
$endgroup$
– cadmus1324
Jan 8 at 16:27
$begingroup$
What are the different types of walks of length 4 that start and end at the same vertex? Can you think of a way to eliminate the ones you don't want?
$endgroup$
– Morgan Rodgers
Jan 9 at 20:27
$begingroup$
Dear Morgan, that's actually the main problem I can't solve: how to discard the 4-length walks that begin and end at v1 and which are not squares. For example, given the adjacency matrix A = [0110;1001;1001;0110] then A^4 = [8008; 0880; 0880;8008]. The conclusion should be that there is only one square in which v1 participates (in this particular case, v1 could be any vertex of G). Nevertheless, it is not clear to me how to formally discard the other 7 walks that are of length 4, but are not squares. Any help would be appreciated since I am clueless.
$endgroup$
– cadmus1324
Jan 10 at 2:22
$begingroup$
Anyone? I would greatly appreciate any help on this matter :(
$endgroup$
– cadmus1324
Jan 11 at 3:28
3
3
$begingroup$
By a "square" you just mean a cycle of length $4$, don't you? Is the graph undirected? You want a formula in terms of what, the adjacency matrix of the graph? What is your formula for triangles?
$endgroup$
– bof
Jan 8 at 5:08
$begingroup$
By a "square" you just mean a cycle of length $4$, don't you? Is the graph undirected? You want a formula in terms of what, the adjacency matrix of the graph? What is your formula for triangles?
$endgroup$
– bof
Jan 8 at 5:08
1
1
$begingroup$
Dear bof: sorry about the confusion. Yes, the graph is undirected. The formula should be in terms of the powers of the adjacency matrix. For example, for triangles, I should take the values of each vertex on the diagonal of A^3 and divide them by 2. Those would be the paths of length 3 that begin and end and each vertex. Therefore, they are triangles (I am discarding the counting on both directions by dividing the number by 2).
$endgroup$
– cadmus1324
Jan 8 at 16:27
$begingroup$
Dear bof: sorry about the confusion. Yes, the graph is undirected. The formula should be in terms of the powers of the adjacency matrix. For example, for triangles, I should take the values of each vertex on the diagonal of A^3 and divide them by 2. Those would be the paths of length 3 that begin and end and each vertex. Therefore, they are triangles (I am discarding the counting on both directions by dividing the number by 2).
$endgroup$
– cadmus1324
Jan 8 at 16:27
$begingroup$
What are the different types of walks of length 4 that start and end at the same vertex? Can you think of a way to eliminate the ones you don't want?
$endgroup$
– Morgan Rodgers
Jan 9 at 20:27
$begingroup$
What are the different types of walks of length 4 that start and end at the same vertex? Can you think of a way to eliminate the ones you don't want?
$endgroup$
– Morgan Rodgers
Jan 9 at 20:27
$begingroup$
Dear Morgan, that's actually the main problem I can't solve: how to discard the 4-length walks that begin and end at v1 and which are not squares. For example, given the adjacency matrix A = [0110;1001;1001;0110] then A^4 = [8008; 0880; 0880;8008]. The conclusion should be that there is only one square in which v1 participates (in this particular case, v1 could be any vertex of G). Nevertheless, it is not clear to me how to formally discard the other 7 walks that are of length 4, but are not squares. Any help would be appreciated since I am clueless.
$endgroup$
– cadmus1324
Jan 10 at 2:22
$begingroup$
Dear Morgan, that's actually the main problem I can't solve: how to discard the 4-length walks that begin and end at v1 and which are not squares. For example, given the adjacency matrix A = [0110;1001;1001;0110] then A^4 = [8008; 0880; 0880;8008]. The conclusion should be that there is only one square in which v1 participates (in this particular case, v1 could be any vertex of G). Nevertheless, it is not clear to me how to formally discard the other 7 walks that are of length 4, but are not squares. Any help would be appreciated since I am clueless.
$endgroup$
– cadmus1324
Jan 10 at 2:22
$begingroup$
Anyone? I would greatly appreciate any help on this matter :(
$endgroup$
– cadmus1324
Jan 11 at 3:28
$begingroup$
Anyone? I would greatly appreciate any help on this matter :(
$endgroup$
– cadmus1324
Jan 11 at 3:28
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
can you find the answer? I have read that for squares is different than triangles, but they are related with A^2, this are the squares but i'm not shure if this indicates The number of squares in which each vertex participates. Can you give a guide to find the formula?
answered Jan 20 at 1:38
FerFer
32
$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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065822%2fgiven-a-graph-g-how-to-find-a-formula-to-determine-the-number-of-squares-in-whi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
can you find the answer? I have read that for squares is different than triangles, but they are related with A^2, this are the squares but i'm not shure if this indicates The number of squares in which each vertex participates. Can you give a guide to find the formula?
answered Jan 20 at 1:38
FerFer
32
$endgroup$
add a comment |
$begingroup$
can you find the answer? I have read that for squares is different than triangles, but they are related with A^2, this are the squares but i'm not shure if this indicates The number of squares in which each vertex participates. Can you give a guide to find the formula?
answered Jan 20 at 1:38
FerFer
32
$endgroup$
add a comment |
$begingroup$
can you find the answer? I have read that for squares is different than triangles, but they are related with A^2, this are the squares but i'm not shure if this indicates The number of squares in which each vertex participates. Can you give a guide to find the formula?
answered Jan 20 at 1:38
FerFer
32
$endgroup$
can you find the answer? I have read that for squares is different than triangles, but they are related with A^2, this are the squares but i'm not shure if this indicates The number of squares in which each vertex participates. Can you give a guide to find the formula?
answered Jan 20 at 1:38
FerFer
32
answered Jan 20 at 1:38
FerFer
32
answered Jan 20 at 1:38
FerFer
32
answered Jan 20 at 1:38
FerFer
32
32
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065822%2fgiven-a-graph-g-how-to-find-a-formula-to-determine-the-number-of-squares-in-whi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
By a "square" you just mean a cycle of length $4$, don't you? Is the graph undirected? You want a formula in terms of what, the adjacency matrix of the graph? What is your formula for triangles?
$endgroup$
– bof
Jan 8 at 5:08
1
$begingroup$
Dear bof: sorry about the confusion. Yes, the graph is undirected. The formula should be in terms of the powers of the adjacency matrix. For example, for triangles, I should take the values of each vertex on the diagonal of A^3 and divide them by 2. Those would be the paths of length 3 that begin and end and each vertex. Therefore, they are triangles (I am discarding the counting on both directions by dividing the number by 2).
$endgroup$
– cadmus1324
Jan 8 at 16:27
$begingroup$
What are the different types of walks of length 4 that start and end at the same vertex? Can you think of a way to eliminate the ones you don't want?
$endgroup$
– Morgan Rodgers
Jan 9 at 20:27
$begingroup$
Dear Morgan, that's actually the main problem I can't solve: how to discard the 4-length walks that begin and end at v1 and which are not squares. For example, given the adjacency matrix A = [0110;1001;1001;0110] then A^4 = [8008; 0880; 0880;8008]. The conclusion should be that there is only one square in which v1 participates (in this particular case, v1 could be any vertex of G). Nevertheless, it is not clear to me how to formally discard the other 7 walks that are of length 4, but are not squares. Any help would be appreciated since I am clueless.
$endgroup$
– cadmus1324
Jan 10 at 2:22
$begingroup$
Anyone? I would greatly appreciate any help on this matter :(
$endgroup$
– cadmus1324
Jan 11 at 3:28