Degree or valency of a Cayley graph
Let $G$ be a group and $S subseteq G$ be a generating set of $G$.
The Cayley digraph of $G$ with respect
to $S$, $X=overrightarrow {operatorname{Cay}}(G, S)$ is a graph whose vertices are the elements of $G$ and there is an edge from $g$ to $gs$
whenever $g in G$ and $s in S$.
The Cayley graph, $X = operatorname{Cay}(G, S)$ is the undirected graph whose vertices
are the elements of $G$ and there is an edge from $g$ to $gs$ and from $g$ to $gs^{-1}$ whenever $g in G$ and $s in S$.
In a group, an element of order $2$ is known as an "involution". i.e. a non-identity element
whose square is the identity element.
So by thinking about the above definitions I have written the following about the degree of a Cayley graph, $X=operatorname{Cay}(G,S)$ of a group $G$, with respect to a generator set $S$:
"$deg(X)= 2vert S vert $, if $S$ has elements which are not involutions"
I would like to know whether above sentence is correct. Is it ok, to mention as "$S$ has elements which are not involutions"?
abstract-algebra group-theory graph-theory finite-groups cayley-graphs
edited Dec 27 '18 at 9:13
Shaun
8,711113680
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
add a comment |
Let $G$ be a group and $S subseteq G$ be a generating set of $G$.
The Cayley digraph of $G$ with respect
to $S$, $X=overrightarrow {operatorname{Cay}}(G, S)$ is a graph whose vertices are the elements of $G$ and there is an edge from $g$ to $gs$
whenever $g in G$ and $s in S$.
The Cayley graph, $X = operatorname{Cay}(G, S)$ is the undirected graph whose vertices
are the elements of $G$ and there is an edge from $g$ to $gs$ and from $g$ to $gs^{-1}$ whenever $g in G$ and $s in S$.
In a group, an element of order $2$ is known as an "involution". i.e. a non-identity element
whose square is the identity element.
So by thinking about the above definitions I have written the following about the degree of a Cayley graph, $X=operatorname{Cay}(G,S)$ of a group $G$, with respect to a generator set $S$:
"$deg(X)= 2vert S vert $, if $S$ has elements which are not involutions"
I would like to know whether above sentence is correct. Is it ok, to mention as "$S$ has elements which are not involutions"?
abstract-algebra group-theory graph-theory finite-groups cayley-graphs
edited Dec 27 '18 at 9:13
Shaun
8,711113680
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
You asked this in the group theory chatroom. However, in order to avoid downvotes on this question or having it closed, please edit it to include more context, such as why the question is interesting to you, where it arose, and what you have done to solve it yourself :)
– Shaun
Dec 26 '18 at 19:29
1
Ok, thanks @Shaun :) :)
– Buddhini Angelika
Dec 27 '18 at 8:53
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?.
– Shaun
Dec 27 '18 at 9:12
Thank you @Shaun :) :)
– Buddhini Angelika
Dec 28 '18 at 10:46
add a comment |
Let $G$ be a group and $S subseteq G$ be a generating set of $G$.
The Cayley digraph of $G$ with respect
to $S$, $X=overrightarrow {operatorname{Cay}}(G, S)$ is a graph whose vertices are the elements of $G$ and there is an edge from $g$ to $gs$
whenever $g in G$ and $s in S$.
The Cayley graph, $X = operatorname{Cay}(G, S)$ is the undirected graph whose vertices
are the elements of $G$ and there is an edge from $g$ to $gs$ and from $g$ to $gs^{-1}$ whenever $g in G$ and $s in S$.
In a group, an element of order $2$ is known as an "involution". i.e. a non-identity element
whose square is the identity element.
So by thinking about the above definitions I have written the following about the degree of a Cayley graph, $X=operatorname{Cay}(G,S)$ of a group $G$, with respect to a generator set $S$:
"$deg(X)= 2vert S vert $, if $S$ has elements which are not involutions"
I would like to know whether above sentence is correct. Is it ok, to mention as "$S$ has elements which are not involutions"?
abstract-algebra group-theory graph-theory finite-groups cayley-graphs
edited Dec 27 '18 at 9:13
Shaun
8,711113680
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
Let $G$ be a group and $S subseteq G$ be a generating set of $G$.
The Cayley digraph of $G$ with respect
to $S$, $X=overrightarrow {operatorname{Cay}}(G, S)$ is a graph whose vertices are the elements of $G$ and there is an edge from $g$ to $gs$
whenever $g in G$ and $s in S$.
The Cayley graph, $X = operatorname{Cay}(G, S)$ is the undirected graph whose vertices
are the elements of $G$ and there is an edge from $g$ to $gs$ and from $g$ to $gs^{-1}$ whenever $g in G$ and $s in S$.
In a group, an element of order $2$ is known as an "involution". i.e. a non-identity element
whose square is the identity element.
So by thinking about the above definitions I have written the following about the degree of a Cayley graph, $X=operatorname{Cay}(G,S)$ of a group $G$, with respect to a generator set $S$:
"$deg(X)= 2vert S vert $, if $S$ has elements which are not involutions"
I would like to know whether above sentence is correct. Is it ok, to mention as "$S$ has elements which are not involutions"?
abstract-algebra group-theory graph-theory finite-groups cayley-graphs
abstract-algebra group-theory graph-theory finite-groups cayley-graphs
edited Dec 27 '18 at 9:13
Shaun
8,711113680
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
edited Dec 27 '18 at 9:13
Shaun
8,711113680
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
edited Dec 27 '18 at 9:13
Shaun
8,711113680
edited Dec 27 '18 at 9:13
Shaun
8,711113680
edited Dec 27 '18 at 9:13
Shaun
8,711113680
8,711113680
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
asked Dec 26 '18 at 17:36
Buddhini Angelika
15710
15710
You asked this in the group theory chatroom. However, in order to avoid downvotes on this question or having it closed, please edit it to include more context, such as why the question is interesting to you, where it arose, and what you have done to solve it yourself :)
– Shaun
Dec 26 '18 at 19:29
1
Ok, thanks @Shaun :) :)
– Buddhini Angelika
Dec 27 '18 at 8:53
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?.
– Shaun
Dec 27 '18 at 9:12
Thank you @Shaun :) :)
– Buddhini Angelika
Dec 28 '18 at 10:46
add a comment |
You asked this in the group theory chatroom. However, in order to avoid downvotes on this question or having it closed, please edit it to include more context, such as why the question is interesting to you, where it arose, and what you have done to solve it yourself :)
– Shaun
Dec 26 '18 at 19:29
1
Ok, thanks @Shaun :) :)
– Buddhini Angelika
Dec 27 '18 at 8:53
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?.
– Shaun
Dec 27 '18 at 9:12
Thank you @Shaun :) :)
– Buddhini Angelika
Dec 28 '18 at 10:46
You asked this in the group theory chatroom. However, in order to avoid downvotes on this question or having it closed, please edit it to include more context, such as why the question is interesting to you, where it arose, and what you have done to solve it yourself :)
– Shaun
Dec 26 '18 at 19:29
You asked this in the group theory chatroom. However, in order to avoid downvotes on this question or having it closed, please edit it to include more context, such as why the question is interesting to you, where it arose, and what you have done to solve it yourself :)
– Shaun
Dec 26 '18 at 19:29
1
1
Ok, thanks @Shaun :) :)
– Buddhini Angelika
Dec 27 '18 at 8:53
Ok, thanks @Shaun :) :)
– Buddhini Angelika
Dec 27 '18 at 8:53
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?.
– Shaun
Dec 27 '18 at 9:12
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?.
– Shaun
Dec 27 '18 at 9:12
Thank you @Shaun :) :)
– Buddhini Angelika
Dec 28 '18 at 10:46
Thank you @Shaun :) :)
– Buddhini Angelika
Dec 28 '18 at 10:46
add a comment |
1 Answer
1
active
oldest
votes
The answer may depend on definitions of a Cayley graph and vertex degree. Namely, if we consider the directed Cayley graph then in-degree of its each vertex equals to its out-degree and equals to $|S|$. If we consider the undirected Cayley graph then we assume that $S$ is symmetric and without the identity ${e}$ and then degree of its each vertex equals $|S|$.
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
1
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
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%2f3053135%2fdegree-or-valency-of-a-cayley-graph%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
The answer may depend on definitions of a Cayley graph and vertex degree. Namely, if we consider the directed Cayley graph then in-degree of its each vertex equals to its out-degree and equals to $|S|$. If we consider the undirected Cayley graph then we assume that $S$ is symmetric and without the identity ${e}$ and then degree of its each vertex equals $|S|$.
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
1
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
add a comment |
The answer may depend on definitions of a Cayley graph and vertex degree. Namely, if we consider the directed Cayley graph then in-degree of its each vertex equals to its out-degree and equals to $|S|$. If we consider the undirected Cayley graph then we assume that $S$ is symmetric and without the identity ${e}$ and then degree of its each vertex equals $|S|$.
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
1
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
add a comment |
The answer may depend on definitions of a Cayley graph and vertex degree. Namely, if we consider the directed Cayley graph then in-degree of its each vertex equals to its out-degree and equals to $|S|$. If we consider the undirected Cayley graph then we assume that $S$ is symmetric and without the identity ${e}$ and then degree of its each vertex equals $|S|$.
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
The answer may depend on definitions of a Cayley graph and vertex degree. Namely, if we consider the directed Cayley graph then in-degree of its each vertex equals to its out-degree and equals to $|S|$. If we consider the undirected Cayley graph then we assume that $S$ is symmetric and without the identity ${e}$ and then degree of its each vertex equals $|S|$.
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
answered Dec 26 '18 at 21:07
Alex Ravsky
39.2k32080
39.2k32080
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
1
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
add a comment |
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
1
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
– Buddhini Angelika
Dec 27 '18 at 8:35
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
@BuddhiniAngelika According to the given definition of ${operatorname{Cay}}(G, S)$ degree of any its vertex is $2|S|-|S_i|$, where $S_i={gin S: g$ is an involution$}$. In particular, if $S$ contains no involutions then degrere of each vertex of ${operatorname{Cay}}(G, S)$ is $2|S|$.
– Alex Ravsky
Dec 27 '18 at 8:55
1
1
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
Thank you very much @AlexRavsky
– Buddhini Angelika
Dec 28 '18 at 2:58
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3053135%2fdegree-or-valency-of-a-cayley-graph%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
You asked this in the group theory chatroom. However, in order to avoid downvotes on this question or having it closed, please edit it to include more context, such as why the question is interesting to you, where it arose, and what you have done to solve it yourself :)
– Shaun
Dec 26 '18 at 19:29
1
Ok, thanks @Shaun :) :)
– Buddhini Angelika
Dec 27 '18 at 8:53
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?.
– Shaun
Dec 27 '18 at 9:12
Thank you @Shaun :) :)
– Buddhini Angelika
Dec 28 '18 at 10:46