Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My google search turned up much information about what people are doing with inductive graphs, but no definitions. So I ask you, StackExchange, what is an inductive graph? When I think of induction, I think of recursion. But this must be a wrong line of thinking, because cannot all graphs be constructed recursively? Thanks for clearing up my confusion.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

A graph $G$ is $d$-inductive if the vertices of $G$ can be numbered so that each vertex has at most $d$ edges to higher-numbered vertices.

share|improve this answer
So does the set of verticies need to have a partial order? –  Athan Clark Jul 5 at 4:11
I think we're talking about numbering the vertices of an $n$-vertex graph with $1,2,3,\dots,n$, each vertex getting a different number. –  Gerry Myerson Jul 5 at 4:14
I see. However, the strict ordering is mandatory? Or could you simply limit the total number of edges any vertex has? –  Athan Clark Jul 5 at 4:25
If no vertex has degree exceeding $r$, then (no matter how you number the vertices) each vertex has at most $r$ edges to higher-numbered vertices, so the graph is guaranteed to be (trivially) $r$-inductive. The concept "$d$-inductive" would appear to be interesting only if there are vertices of degree bigger than $d$. –  Gerry Myerson Jul 5 at 4:28

To be fair, I just used search engines as well. But let me know if either of these ring a bell:

Wikipedia thinks that inductive graphs may also be known as degenerate graphs:

enter image description here

On the other hand, the book The Theory of Graphs defines an inductive graph on page 13:

enter image description here

Do these line up with the sorts of inductive graphs you've been looking at?

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.