Name for network in which nodes only have two different degrees

Question

What is the name for a network that only admits two different values for the degrees of its nodes?

For example you might have a graph with degree sequence, $D=(12^4,4^{100}).$ The notation means there are four nodes of degree $12$ and $100$ nodes of degree $4.$ I plotted the degree distribution and got two points, so does that mean there is a linear relationship? Are these networks studied?

The degree distribution for a random network looks like a bell-curve, and for a scale-free network it looks like a power law distribution, but I have not heard of a degree distribution that has an indirect linear relationship.

Thanks.

Answer 1

I wouldn't describe the degree sequence you have by the words "linear relationship". If you told me that the degree distribution is linear, I'd expect that in some range (such as $[4,12]$) all possible degrees are possible, and the frequency with which we get any particular degree changes linearly. This should be a special case of a power-law distribution.

If we just have a bunch of vertices of degrees $4$ and $12$, that's not what you'd expect to be an emergent property of any random graph law: you expect that the graph was deliberately chosen to have this degree sequence.

It's possible to choose a uniformly random graph with a given degree sequence via the configuration model. (Not that your graph necessarily looks like a typical random graph of that degree sequence.)

Answer 2

Such random graphs are well studied.

Here's one meeting your specifications:

Of course this is a random graph because the particular connection matrix is not constrained by the vertex degree specifications... so any particular instance is chosen pseudorandomly from all consistent such graphs.

For instance, here are four undirected graphs each having $2$ vertices with degree $12$ and $10$ vertices with degree $4$. You can tell they are not isomorphic by counting the self-loops in each (or doing a deeper statistical analysis). The presentation (generation) of any particular one of these is thus a pseudorandom process.

There are many different models for generating random graphs based on the statistical distribution of nodes, or vertices, or other constraint property, as you can read in the linked site or any book on random graphs.