Construction of graph with degrees $d$ and $(d + 1)$
Let $n = a + b$ and $d$ be non-negative integers such that: $ad + b(d + 1)$ is even and $(d + 1) leq (n - 1)$. Does there exist a graph with $n$ vertices such that $a$ of them have degree $d$ and $b$ of them have degree $(d + 1)$? Is there an explicit construction?
graph-theory
asked Nov 17 at 16:09
frafour
841212
add a comment |
Let $n = a + b$ and $d$ be non-negative integers such that: $ad + b(d + 1)$ is even and $(d + 1) leq (n - 1)$. Does there exist a graph with $n$ vertices such that $a$ of them have degree $d$ and $b$ of them have degree $(d + 1)$? Is there an explicit construction?
graph-theory
asked Nov 17 at 16:09
frafour
841212
add a comment |
Let $n = a + b$ and $d$ be non-negative integers such that: $ad + b(d + 1)$ is even and $(d + 1) leq (n - 1)$. Does there exist a graph with $n$ vertices such that $a$ of them have degree $d$ and $b$ of them have degree $(d + 1)$? Is there an explicit construction?
graph-theory
asked Nov 17 at 16:09
frafour
841212
Let $n = a + b$ and $d$ be non-negative integers such that: $ad + b(d + 1)$ is even and $(d + 1) leq (n - 1)$. Does there exist a graph with $n$ vertices such that $a$ of them have degree $d$ and $b$ of them have degree $(d + 1)$? Is there an explicit construction?
graph-theory
graph-theory
asked Nov 17 at 16:09
frafour
841212
asked Nov 17 at 16:09
frafour
841212
asked Nov 17 at 16:09
frafour
841212
asked Nov 17 at 16:09
frafour
841212
asked Nov 17 at 16:09
frafour
841212
841212
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
This is not the answer but maybe that can give some idea:
Fix an integer $kgeq3$. There exist a $(2k-1)$-vertex $(k-2)$-edge-connected simple graph $H_k=(V_k,E_k)$ with $V_k={y_1,y_2,...,y_{k+1},z_{1},z_{2},...,z_{k-2}}$, where all vertices $y_i$ have degree $k$ and all vertices $z_j$ have degree $(k-1)$.
proof:
Start with a k-vertex complete graph on the vertices ${y_1,...,y_k}$, plus a $(k-2)$-vertex complete graph on the vertices ${z_1,...,z_{k-2}}$. Next place an edge from the vertex $y_{k+1}$ to the vertices $y_{k-1}$ and $y_{k}$, then $(k-2)$ edges of the form $y_jz_j$ and $(k-2)$ edges of the form $y_{k+1}z_j$.
answered Nov 19 at 0:51
mathnoob
1,775322
add a comment |
We start with $k$-regular graphs on $n$ vertices constructed as follows. Put the $n$ vertices around a circle. If $k$ is even, connect each vertex to its $k$ closest neighbours. If $k$ is odd, then $n$ is even, so we can construct a $(k - 1)$-regular graph as before, and then add an edge between each vertex and its antipode.
From this construction the one I was asking for follows. One has to proceed by cases, and I have checked all the details and it works, but I won't write everything here. The idea is that you either construct a $d$-regular graph, then check that you have a large enough matching in the complement, and add part of it to augment the degree of some vertices by 1; or you construct a $(d + 1)$-regular graph, then check you have a large enough matching, and eliminate part of it to decrease the degree of some vertices by 1. It's a bit tedious to check everything but it's quite straightforward.
answered Nov 29 at 12:45
frafour
841212
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%2f3002518%2fconstruction-of-graph-with-degrees-d-and-d-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is not the answer but maybe that can give some idea:
Fix an integer $kgeq3$. There exist a $(2k-1)$-vertex $(k-2)$-edge-connected simple graph $H_k=(V_k,E_k)$ with $V_k={y_1,y_2,...,y_{k+1},z_{1},z_{2},...,z_{k-2}}$, where all vertices $y_i$ have degree $k$ and all vertices $z_j$ have degree $(k-1)$.
proof:
Start with a k-vertex complete graph on the vertices ${y_1,...,y_k}$, plus a $(k-2)$-vertex complete graph on the vertices ${z_1,...,z_{k-2}}$. Next place an edge from the vertex $y_{k+1}$ to the vertices $y_{k-1}$ and $y_{k}$, then $(k-2)$ edges of the form $y_jz_j$ and $(k-2)$ edges of the form $y_{k+1}z_j$.
answered Nov 19 at 0:51
mathnoob
1,775322
add a comment |
This is not the answer but maybe that can give some idea:
Fix an integer $kgeq3$. There exist a $(2k-1)$-vertex $(k-2)$-edge-connected simple graph $H_k=(V_k,E_k)$ with $V_k={y_1,y_2,...,y_{k+1},z_{1},z_{2},...,z_{k-2}}$, where all vertices $y_i$ have degree $k$ and all vertices $z_j$ have degree $(k-1)$.
proof:
Start with a k-vertex complete graph on the vertices ${y_1,...,y_k}$, plus a $(k-2)$-vertex complete graph on the vertices ${z_1,...,z_{k-2}}$. Next place an edge from the vertex $y_{k+1}$ to the vertices $y_{k-1}$ and $y_{k}$, then $(k-2)$ edges of the form $y_jz_j$ and $(k-2)$ edges of the form $y_{k+1}z_j$.
answered Nov 19 at 0:51
mathnoob
1,775322
add a comment |
This is not the answer but maybe that can give some idea:
Fix an integer $kgeq3$. There exist a $(2k-1)$-vertex $(k-2)$-edge-connected simple graph $H_k=(V_k,E_k)$ with $V_k={y_1,y_2,...,y_{k+1},z_{1},z_{2},...,z_{k-2}}$, where all vertices $y_i$ have degree $k$ and all vertices $z_j$ have degree $(k-1)$.
proof:
Start with a k-vertex complete graph on the vertices ${y_1,...,y_k}$, plus a $(k-2)$-vertex complete graph on the vertices ${z_1,...,z_{k-2}}$. Next place an edge from the vertex $y_{k+1}$ to the vertices $y_{k-1}$ and $y_{k}$, then $(k-2)$ edges of the form $y_jz_j$ and $(k-2)$ edges of the form $y_{k+1}z_j$.
answered Nov 19 at 0:51
mathnoob
1,775322
This is not the answer but maybe that can give some idea:
Fix an integer $kgeq3$. There exist a $(2k-1)$-vertex $(k-2)$-edge-connected simple graph $H_k=(V_k,E_k)$ with $V_k={y_1,y_2,...,y_{k+1},z_{1},z_{2},...,z_{k-2}}$, where all vertices $y_i$ have degree $k$ and all vertices $z_j$ have degree $(k-1)$.
proof:
Start with a k-vertex complete graph on the vertices ${y_1,...,y_k}$, plus a $(k-2)$-vertex complete graph on the vertices ${z_1,...,z_{k-2}}$. Next place an edge from the vertex $y_{k+1}$ to the vertices $y_{k-1}$ and $y_{k}$, then $(k-2)$ edges of the form $y_jz_j$ and $(k-2)$ edges of the form $y_{k+1}z_j$.
answered Nov 19 at 0:51
mathnoob
1,775322
answered Nov 19 at 0:51
mathnoob
1,775322
answered Nov 19 at 0:51
mathnoob
1,775322
answered Nov 19 at 0:51
mathnoob
1,775322
1,775322
add a comment |
add a comment |
We start with $k$-regular graphs on $n$ vertices constructed as follows. Put the $n$ vertices around a circle. If $k$ is even, connect each vertex to its $k$ closest neighbours. If $k$ is odd, then $n$ is even, so we can construct a $(k - 1)$-regular graph as before, and then add an edge between each vertex and its antipode.
From this construction the one I was asking for follows. One has to proceed by cases, and I have checked all the details and it works, but I won't write everything here. The idea is that you either construct a $d$-regular graph, then check that you have a large enough matching in the complement, and add part of it to augment the degree of some vertices by 1; or you construct a $(d + 1)$-regular graph, then check you have a large enough matching, and eliminate part of it to decrease the degree of some vertices by 1. It's a bit tedious to check everything but it's quite straightforward.
answered Nov 29 at 12:45
frafour
841212
add a comment |
We start with $k$-regular graphs on $n$ vertices constructed as follows. Put the $n$ vertices around a circle. If $k$ is even, connect each vertex to its $k$ closest neighbours. If $k$ is odd, then $n$ is even, so we can construct a $(k - 1)$-regular graph as before, and then add an edge between each vertex and its antipode.
From this construction the one I was asking for follows. One has to proceed by cases, and I have checked all the details and it works, but I won't write everything here. The idea is that you either construct a $d$-regular graph, then check that you have a large enough matching in the complement, and add part of it to augment the degree of some vertices by 1; or you construct a $(d + 1)$-regular graph, then check you have a large enough matching, and eliminate part of it to decrease the degree of some vertices by 1. It's a bit tedious to check everything but it's quite straightforward.
answered Nov 29 at 12:45
frafour
841212
add a comment |
We start with $k$-regular graphs on $n$ vertices constructed as follows. Put the $n$ vertices around a circle. If $k$ is even, connect each vertex to its $k$ closest neighbours. If $k$ is odd, then $n$ is even, so we can construct a $(k - 1)$-regular graph as before, and then add an edge between each vertex and its antipode.
From this construction the one I was asking for follows. One has to proceed by cases, and I have checked all the details and it works, but I won't write everything here. The idea is that you either construct a $d$-regular graph, then check that you have a large enough matching in the complement, and add part of it to augment the degree of some vertices by 1; or you construct a $(d + 1)$-regular graph, then check you have a large enough matching, and eliminate part of it to decrease the degree of some vertices by 1. It's a bit tedious to check everything but it's quite straightforward.
answered Nov 29 at 12:45
frafour
841212
We start with $k$-regular graphs on $n$ vertices constructed as follows. Put the $n$ vertices around a circle. If $k$ is even, connect each vertex to its $k$ closest neighbours. If $k$ is odd, then $n$ is even, so we can construct a $(k - 1)$-regular graph as before, and then add an edge between each vertex and its antipode.
From this construction the one I was asking for follows. One has to proceed by cases, and I have checked all the details and it works, but I won't write everything here. The idea is that you either construct a $d$-regular graph, then check that you have a large enough matching in the complement, and add part of it to augment the degree of some vertices by 1; or you construct a $(d + 1)$-regular graph, then check you have a large enough matching, and eliminate part of it to decrease the degree of some vertices by 1. It's a bit tedious to check everything but it's quite straightforward.
answered Nov 29 at 12:45
frafour
841212
answered Nov 29 at 12:45
frafour
841212
answered Nov 29 at 12:45
frafour
841212
answered Nov 29 at 12:45
frafour
841212
841212
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.
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%2f3002518%2fconstruction-of-graph-with-degrees-d-and-d-1%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
