Degree or valency of a Cayley graph
$begingroup$
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
9,406113684
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
$endgroup$
add a comment |
$begingroup$
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
9,406113684
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
$endgroup$
$begingroup$
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 :)
$endgroup$
– Shaun
Dec 26 '18 at 19:29
1
$begingroup$
Ok, thanks @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:53
$begingroup$
Thank you @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 10:46
add a comment |
$begingroup$
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
9,406113684
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
$endgroup$
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
9,406113684
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
edited Dec 27 '18 at 9:13
Shaun
9,406113684
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
edited Dec 27 '18 at 9:13
Shaun
9,406113684
edited Dec 27 '18 at 9:13
Shaun
9,406113684
edited Dec 27 '18 at 9:13
Shaun
9,406113684
9,406113684
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
asked Dec 26 '18 at 17:36
Buddhini AngelikaBuddhini Angelika
12411
12411
$begingroup$
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 :)
$endgroup$
– Shaun
Dec 26 '18 at 19:29
1
$begingroup$
Ok, thanks @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:53
$begingroup$
Thank you @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 10:46
add a comment |
$begingroup$
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 :)
$endgroup$
– Shaun
Dec 26 '18 at 19:29
1
$begingroup$
Ok, thanks @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:53
$begingroup$
Thank you @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 10:46
$begingroup$
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 :)
$endgroup$
– Shaun
Dec 26 '18 at 19:29
$begingroup$
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 :)
$endgroup$
– Shaun
Dec 26 '18 at 19:29
1
1
$begingroup$
Ok, thanks @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:53
$begingroup$
Ok, thanks @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:53
$begingroup$
Thank you @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 10:46
$begingroup$
Thank you @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 10:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 RavskyAlex Ravsky
42.7k32383
$endgroup$
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
1
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– 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
$begingroup$
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 RavskyAlex Ravsky
42.7k32383
$endgroup$
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
1
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 2:58
add a comment |
$begingroup$
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 RavskyAlex Ravsky
42.7k32383
$endgroup$
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
1
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 2:58
add a comment |
$begingroup$
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 RavskyAlex Ravsky
42.7k32383
$endgroup$
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 RavskyAlex Ravsky
42.7k32383
answered Dec 26 '18 at 21:07
Alex RavskyAlex Ravsky
42.7k32383
answered Dec 26 '18 at 21:07
Alex RavskyAlex Ravsky
42.7k32383
answered Dec 26 '18 at 21:07
Alex RavskyAlex Ravsky
42.7k32383
42.7k32383
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
1
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 2:58
add a comment |
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
1
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 2:58
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
Thanks @AlexRavsky I have added more details to the question as instructed. Do you think it's correct to mention about involutions ?
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:35
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
$begingroup$
@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|$.
$endgroup$
– Alex Ravsky
Dec 27 '18 at 8:55
1
1
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 2:58
$begingroup$
Thank you very much @AlexRavsky
$endgroup$
– 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.
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
$begingroup$
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 :)
$endgroup$
– Shaun
Dec 26 '18 at 19:29
1
$begingroup$
Ok, thanks @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 27 '18 at 8:53
$begingroup$
Thank you @Shaun :) :)
$endgroup$
– Buddhini Angelika
Dec 28 '18 at 10:46