Name of non-complete graph with certain properties

$\begingroup$

Is there a name for a graph with the following criteria?

• not a complete graph
• has at least n vertices (let's say n > 3 to exclude trivial cases)
• where every vertex's degree is at least n.

Or, is there a class of graphs that tend to have this kind of pattern? I've run into graphs like this in my research, and I'm hoping to tap into a body of existing knowledge on them.

For example:

$\endgroup$ 3

1 Answer

$\begingroup$

The second condition is redundant given the third: if every vertex has degree $n$, there must be at least $n+1$ vertices.

I would call graphs with the third condition "graphs with minimum degree at least $n$" or "graphs $G$ with $\delta(G) \ge n$". This is concise enough that no further terminology has developed.

There isn't a nice way to exclude the complete graph. You could say "other than complete graphs", but first double-check that whatever you're saying isn't also true for complete graphs, just in case. I guess you could also say "graphs $G$ with $n \le \delta(G) \le |V(G)|-2$", since complete graphs are distinguished by having $\delta(G)=|V(G)|-1$.

If you're looking for properties of such graphs, you should look for properties of graphs with minimum degree at least $n$; excluding complete graphs probably won't get you any more properties beyond that.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy