In a graph of `N` ternary nodes represented as an adjacency table of delta positions, is it possible to...
$begingroup$
Let's define a graph to be a set of N nodes, where every node has exactly 3 outgoing edges. Such graph can be represented as a table of adjacency, using delta positions to denote edges. For example, the graph:
Could be represented as:
0 1 2
A: 0 +1 +2 +1
B: 1 -1 -1 +1
C: 2 +1 -1 -2
D: 3 -1 +0 -0
On the first row, we have +1, +2, +1, because A has edges to B, C, B respectively, which are at 1, 2, 1 rows behind A, respectively. Similarly, B's first edge is -1, because it goes to A, which is on the previous row. There are multiple ways to represent the same graph, by rearranging rows. Let's define the weight of a graph under a particular representation as the largest absolute value on the table representing it. Let's define the optimal representation as the one with the smallest weight. Let the heaviest among a set of graphs be the one with the largest optimal weight.
My question is: given a N and the heaviest graph of that size, what is the minimum weight W(N) of its optimal representation?
Obviously, any representation of a graph of size N must have a weight of at most N. But how small can it get? In particular, I'm interested in answering if, for large graphs (say, size 1000), we can always find a representation with a low weight (perhaps logarithmic on the size of the graph?).
graph-theory
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
$endgroup$
|
show 7 more comments
$begingroup$
Let's define a graph to be a set of N nodes, where every node has exactly 3 outgoing edges. Such graph can be represented as a table of adjacency, using delta positions to denote edges. For example, the graph:
Could be represented as:
0 1 2
A: 0 +1 +2 +1
B: 1 -1 -1 +1
C: 2 +1 -1 -2
D: 3 -1 +0 -0
On the first row, we have +1, +2, +1, because A has edges to B, C, B respectively, which are at 1, 2, 1 rows behind A, respectively. Similarly, B's first edge is -1, because it goes to A, which is on the previous row. There are multiple ways to represent the same graph, by rearranging rows. Let's define the weight of a graph under a particular representation as the largest absolute value on the table representing it. Let's define the optimal representation as the one with the smallest weight. Let the heaviest among a set of graphs be the one with the largest optimal weight.
My question is: given a N and the heaviest graph of that size, what is the minimum weight W(N) of its optimal representation?
Obviously, any representation of a graph of size N must have a weight of at most N. But how small can it get? In particular, I'm interested in answering if, for large graphs (say, size 1000), we can always find a representation with a low weight (perhaps logarithmic on the size of the graph?).
graph-theory
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
$endgroup$
1
$begingroup$
Could you explain what you mean by the edge length of an edge? How is this different from the distance between the nodes?
$endgroup$
– Kevin Long
Nov 28 '18 at 19:59
$begingroup$
@Kevin Long, that's what I mean, theedge_lengthof an edge between nodesAandBis the distance betweenAandB. The bigger that distance is, the bigger theuinttype required to represent that edge, thus my interest. For example, "is anuint16enough to represent big graphs if we rearrange its representation in a favorable way"?
$endgroup$
– MaiaVictor
Nov 28 '18 at 20:10
$begingroup$
Then why is the edge length of $A_0 iff C_2$ equal to $2$ if the nodes are one edge apart? Also, $A_0, C_2$ is not an edge in your graph- do you just mean for any pair of ports? I also don't understand why you would associate this value to the ports- the edge length from $A_0$ to $C_2$ is just the distance between $A$ and $C$. Why do we have to mention the ports? This seems to only care about pairs of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:14
$begingroup$
@KevinLong this was a mistake. Also, you're right, the edge betweenA0andC2could be presented as just the distance, for the sake of this question. I'd make the question simpler indeed. It was formulated this way because that's how the original format is, but now I realize I could have discarded that information. Let me try improving it.
$endgroup$
– MaiaVictor
Nov 28 '18 at 20:27
1
$begingroup$
I'm guessing we assume connectedness, otherwise you could just give each edge a loop and pair $A$ with $B$, $C$ with $D$, and so on, guaranteeing weight $1$. If you keep ternary, there have to be an even number of vertices, though you could generalize to $k$-regular. If you assume connected, then you have to have weight greater than $1$, and it looks like weight $2$ can be done for any even number of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:48
|
show 7 more comments
$begingroup$
Let's define a graph to be a set of N nodes, where every node has exactly 3 outgoing edges. Such graph can be represented as a table of adjacency, using delta positions to denote edges. For example, the graph:
Could be represented as:
0 1 2
A: 0 +1 +2 +1
B: 1 -1 -1 +1
C: 2 +1 -1 -2
D: 3 -1 +0 -0
On the first row, we have +1, +2, +1, because A has edges to B, C, B respectively, which are at 1, 2, 1 rows behind A, respectively. Similarly, B's first edge is -1, because it goes to A, which is on the previous row. There are multiple ways to represent the same graph, by rearranging rows. Let's define the weight of a graph under a particular representation as the largest absolute value on the table representing it. Let's define the optimal representation as the one with the smallest weight. Let the heaviest among a set of graphs be the one with the largest optimal weight.
My question is: given a N and the heaviest graph of that size, what is the minimum weight W(N) of its optimal representation?
Obviously, any representation of a graph of size N must have a weight of at most N. But how small can it get? In particular, I'm interested in answering if, for large graphs (say, size 1000), we can always find a representation with a low weight (perhaps logarithmic on the size of the graph?).
graph-theory
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
$endgroup$
Let's define a graph to be a set of N nodes, where every node has exactly 3 outgoing edges. Such graph can be represented as a table of adjacency, using delta positions to denote edges. For example, the graph:
Could be represented as:
0 1 2
A: 0 +1 +2 +1
B: 1 -1 -1 +1
C: 2 +1 -1 -2
D: 3 -1 +0 -0
On the first row, we have +1, +2, +1, because A has edges to B, C, B respectively, which are at 1, 2, 1 rows behind A, respectively. Similarly, B's first edge is -1, because it goes to A, which is on the previous row. There are multiple ways to represent the same graph, by rearranging rows. Let's define the weight of a graph under a particular representation as the largest absolute value on the table representing it. Let's define the optimal representation as the one with the smallest weight. Let the heaviest among a set of graphs be the one with the largest optimal weight.
My question is: given a N and the heaviest graph of that size, what is the minimum weight W(N) of its optimal representation?
Obviously, any representation of a graph of size N must have a weight of at most N. But how small can it get? In particular, I'm interested in answering if, for large graphs (say, size 1000), we can always find a representation with a low weight (perhaps logarithmic on the size of the graph?).
graph-theory
graph-theory
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
edited Nov 28 '18 at 21:57
MaiaVictor
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
asked Nov 28 '18 at 19:13
MaiaVictorMaiaVictor
535311
535311
1
$begingroup$
Could you explain what you mean by the edge length of an edge? How is this different from the distance between the nodes?
$endgroup$
– Kevin Long
Nov 28 '18 at 19:59
$begingroup$
@Kevin Long, that's what I mean, theedge_lengthof an edge between nodesAandBis the distance betweenAandB. The bigger that distance is, the bigger theuinttype required to represent that edge, thus my interest. For example, "is anuint16enough to represent big graphs if we rearrange its representation in a favorable way"?
$endgroup$
– MaiaVictor
Nov 28 '18 at 20:10
$begingroup$
Then why is the edge length of $A_0 iff C_2$ equal to $2$ if the nodes are one edge apart? Also, $A_0, C_2$ is not an edge in your graph- do you just mean for any pair of ports? I also don't understand why you would associate this value to the ports- the edge length from $A_0$ to $C_2$ is just the distance between $A$ and $C$. Why do we have to mention the ports? This seems to only care about pairs of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:14
$begingroup$
@KevinLong this was a mistake. Also, you're right, the edge betweenA0andC2could be presented as just the distance, for the sake of this question. I'd make the question simpler indeed. It was formulated this way because that's how the original format is, but now I realize I could have discarded that information. Let me try improving it.
$endgroup$
– MaiaVictor
Nov 28 '18 at 20:27
1
$begingroup$
I'm guessing we assume connectedness, otherwise you could just give each edge a loop and pair $A$ with $B$, $C$ with $D$, and so on, guaranteeing weight $1$. If you keep ternary, there have to be an even number of vertices, though you could generalize to $k$-regular. If you assume connected, then you have to have weight greater than $1$, and it looks like weight $2$ can be done for any even number of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:48
|
show 7 more comments
1
$begingroup$
Could you explain what you mean by the edge length of an edge? How is this different from the distance between the nodes?
$endgroup$
– Kevin Long
Nov 28 '18 at 19:59
$begingroup$
@Kevin Long, that's what I mean, theedge_lengthof an edge between nodesAandBis the distance betweenAandB. The bigger that distance is, the bigger theuinttype required to represent that edge, thus my interest. For example, "is anuint16enough to represent big graphs if we rearrange its representation in a favorable way"?
$endgroup$
– MaiaVictor
Nov 28 '18 at 20:10
$begingroup$
Then why is the edge length of $A_0 iff C_2$ equal to $2$ if the nodes are one edge apart? Also, $A_0, C_2$ is not an edge in your graph- do you just mean for any pair of ports? I also don't understand why you would associate this value to the ports- the edge length from $A_0$ to $C_2$ is just the distance between $A$ and $C$. Why do we have to mention the ports? This seems to only care about pairs of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:14
$begingroup$
@KevinLong this was a mistake. Also, you're right, the edge betweenA0andC2could be presented as just the distance, for the sake of this question. I'd make the question simpler indeed. It was formulated this way because that's how the original format is, but now I realize I could have discarded that information. Let me try improving it.
$endgroup$
– MaiaVictor
Nov 28 '18 at 20:27
1
$begingroup$
I'm guessing we assume connectedness, otherwise you could just give each edge a loop and pair $A$ with $B$, $C$ with $D$, and so on, guaranteeing weight $1$. If you keep ternary, there have to be an even number of vertices, though you could generalize to $k$-regular. If you assume connected, then you have to have weight greater than $1$, and it looks like weight $2$ can be done for any even number of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:48
1
1
$begingroup$
Could you explain what you mean by the edge length of an edge? How is this different from the distance between the nodes?
$endgroup$
– Kevin Long
Nov 28 '18 at 19:59
$begingroup$
Could you explain what you mean by the edge length of an edge? How is this different from the distance between the nodes?
$endgroup$
– Kevin Long
Nov 28 '18 at 19:59
$begingroup$
@Kevin Long, that's what I mean, the
edge_length of an edge between nodes A and B is the distance between A and B. The bigger that distance is, the bigger the uint type required to represent that edge, thus my interest. For example, "is an uint16 enough to represent big graphs if we rearrange its representation in a favorable way"?$endgroup$
– MaiaVictor
Nov 28 '18 at 20:10
$begingroup$
@Kevin Long, that's what I mean, the
edge_length of an edge between nodes A and B is the distance between A and B. The bigger that distance is, the bigger the uint type required to represent that edge, thus my interest. For example, "is an uint16 enough to represent big graphs if we rearrange its representation in a favorable way"?$endgroup$
– MaiaVictor
Nov 28 '18 at 20:10
$begingroup$
Then why is the edge length of $A_0 iff C_2$ equal to $2$ if the nodes are one edge apart? Also, $A_0, C_2$ is not an edge in your graph- do you just mean for any pair of ports? I also don't understand why you would associate this value to the ports- the edge length from $A_0$ to $C_2$ is just the distance between $A$ and $C$. Why do we have to mention the ports? This seems to only care about pairs of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:14
$begingroup$
Then why is the edge length of $A_0 iff C_2$ equal to $2$ if the nodes are one edge apart? Also, $A_0, C_2$ is not an edge in your graph- do you just mean for any pair of ports? I also don't understand why you would associate this value to the ports- the edge length from $A_0$ to $C_2$ is just the distance between $A$ and $C$. Why do we have to mention the ports? This seems to only care about pairs of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:14
$begingroup$
@KevinLong this was a mistake. Also, you're right, the edge between
A0 and C2 could be presented as just the distance, for the sake of this question. I'd make the question simpler indeed. It was formulated this way because that's how the original format is, but now I realize I could have discarded that information. Let me try improving it.$endgroup$
– MaiaVictor
Nov 28 '18 at 20:27
$begingroup$
@KevinLong this was a mistake. Also, you're right, the edge between
A0 and C2 could be presented as just the distance, for the sake of this question. I'd make the question simpler indeed. It was formulated this way because that's how the original format is, but now I realize I could have discarded that information. Let me try improving it.$endgroup$
– MaiaVictor
Nov 28 '18 at 20:27
1
1
$begingroup$
I'm guessing we assume connectedness, otherwise you could just give each edge a loop and pair $A$ with $B$, $C$ with $D$, and so on, guaranteeing weight $1$. If you keep ternary, there have to be an even number of vertices, though you could generalize to $k$-regular. If you assume connected, then you have to have weight greater than $1$, and it looks like weight $2$ can be done for any even number of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:48
$begingroup$
I'm guessing we assume connectedness, otherwise you could just give each edge a loop and pair $A$ with $B$, $C$ with $D$, and so on, guaranteeing weight $1$. If you keep ternary, there have to be an even number of vertices, though you could generalize to $k$-regular. If you assume connected, then you have to have weight greater than $1$, and it looks like weight $2$ can be done for any even number of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:48
|
show 7 more comments
1 Answer
1
active
oldest
votes
$begingroup$
We cannot always find a representation with a low weight.
A graph that's really hard to represent is a graph with small diameter (the value $d$ such that any two vertices are connected by a path of length at most $d$). If you have an $n$-vertex graph with diameter $d$, then no matter how you label the vertices, there will be a path of length $d$ or less from vertex $1$ to vertex $n$; this means at least one of the edges on that path has a weight of at least $frac{n-1}{d}$.
It's possible to construct $3$-regular graphs on $n$ vertices with diameter $O(log n)$. In fact, a random $3$-regular graph is likely to have such a diameter. This short paper gives an explicit construction for $n$-vertex $3$-regular graphs with diameter about $1.413 log_2 n$.
So we can find many examples of $n$-vertex $3$-regular graphs for which the minimum weight of any representation is $O(frac{n}{log n})$.
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
$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%2f3017567%2fin-a-graph-of-n-ternary-nodes-represented-as-an-adjacency-table-of-delta-posit%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$
We cannot always find a representation with a low weight.
A graph that's really hard to represent is a graph with small diameter (the value $d$ such that any two vertices are connected by a path of length at most $d$). If you have an $n$-vertex graph with diameter $d$, then no matter how you label the vertices, there will be a path of length $d$ or less from vertex $1$ to vertex $n$; this means at least one of the edges on that path has a weight of at least $frac{n-1}{d}$.
It's possible to construct $3$-regular graphs on $n$ vertices with diameter $O(log n)$. In fact, a random $3$-regular graph is likely to have such a diameter. This short paper gives an explicit construction for $n$-vertex $3$-regular graphs with diameter about $1.413 log_2 n$.
So we can find many examples of $n$-vertex $3$-regular graphs for which the minimum weight of any representation is $O(frac{n}{log n})$.
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
$endgroup$
add a comment |
$begingroup$
We cannot always find a representation with a low weight.
A graph that's really hard to represent is a graph with small diameter (the value $d$ such that any two vertices are connected by a path of length at most $d$). If you have an $n$-vertex graph with diameter $d$, then no matter how you label the vertices, there will be a path of length $d$ or less from vertex $1$ to vertex $n$; this means at least one of the edges on that path has a weight of at least $frac{n-1}{d}$.
It's possible to construct $3$-regular graphs on $n$ vertices with diameter $O(log n)$. In fact, a random $3$-regular graph is likely to have such a diameter. This short paper gives an explicit construction for $n$-vertex $3$-regular graphs with diameter about $1.413 log_2 n$.
So we can find many examples of $n$-vertex $3$-regular graphs for which the minimum weight of any representation is $O(frac{n}{log n})$.
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
$endgroup$
add a comment |
$begingroup$
We cannot always find a representation with a low weight.
A graph that's really hard to represent is a graph with small diameter (the value $d$ such that any two vertices are connected by a path of length at most $d$). If you have an $n$-vertex graph with diameter $d$, then no matter how you label the vertices, there will be a path of length $d$ or less from vertex $1$ to vertex $n$; this means at least one of the edges on that path has a weight of at least $frac{n-1}{d}$.
It's possible to construct $3$-regular graphs on $n$ vertices with diameter $O(log n)$. In fact, a random $3$-regular graph is likely to have such a diameter. This short paper gives an explicit construction for $n$-vertex $3$-regular graphs with diameter about $1.413 log_2 n$.
So we can find many examples of $n$-vertex $3$-regular graphs for which the minimum weight of any representation is $O(frac{n}{log n})$.
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
$endgroup$
We cannot always find a representation with a low weight.
A graph that's really hard to represent is a graph with small diameter (the value $d$ such that any two vertices are connected by a path of length at most $d$). If you have an $n$-vertex graph with diameter $d$, then no matter how you label the vertices, there will be a path of length $d$ or less from vertex $1$ to vertex $n$; this means at least one of the edges on that path has a weight of at least $frac{n-1}{d}$.
It's possible to construct $3$-regular graphs on $n$ vertices with diameter $O(log n)$. In fact, a random $3$-regular graph is likely to have such a diameter. This short paper gives an explicit construction for $n$-vertex $3$-regular graphs with diameter about $1.413 log_2 n$.
So we can find many examples of $n$-vertex $3$-regular graphs for which the minimum weight of any representation is $O(frac{n}{log n})$.
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
answered Nov 29 '18 at 5:51
Misha LavrovMisha Lavrov
44.4k555106
44.4k555106
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%2f3017567%2fin-a-graph-of-n-ternary-nodes-represented-as-an-adjacency-table-of-delta-posit%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
1
$begingroup$
Could you explain what you mean by the edge length of an edge? How is this different from the distance between the nodes?
$endgroup$
– Kevin Long
Nov 28 '18 at 19:59
$begingroup$
@Kevin Long, that's what I mean, the
edge_lengthof an edge between nodesAandBis the distance betweenAandB. The bigger that distance is, the bigger theuinttype required to represent that edge, thus my interest. For example, "is anuint16enough to represent big graphs if we rearrange its representation in a favorable way"?$endgroup$
– MaiaVictor
Nov 28 '18 at 20:10
$begingroup$
Then why is the edge length of $A_0 iff C_2$ equal to $2$ if the nodes are one edge apart? Also, $A_0, C_2$ is not an edge in your graph- do you just mean for any pair of ports? I also don't understand why you would associate this value to the ports- the edge length from $A_0$ to $C_2$ is just the distance between $A$ and $C$. Why do we have to mention the ports? This seems to only care about pairs of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:14
$begingroup$
@KevinLong this was a mistake. Also, you're right, the edge between
A0andC2could be presented as just the distance, for the sake of this question. I'd make the question simpler indeed. It was formulated this way because that's how the original format is, but now I realize I could have discarded that information. Let me try improving it.$endgroup$
– MaiaVictor
Nov 28 '18 at 20:27
1
$begingroup$
I'm guessing we assume connectedness, otherwise you could just give each edge a loop and pair $A$ with $B$, $C$ with $D$, and so on, guaranteeing weight $1$. If you keep ternary, there have to be an even number of vertices, though you could generalize to $k$-regular. If you assume connected, then you have to have weight greater than $1$, and it looks like weight $2$ can be done for any even number of vertices.
$endgroup$
– Kevin Long
Nov 28 '18 at 20:48