Independent Node Degree in Undirected Graphs

Question

Let $G=(V,E)$ be an undirected graph. The independent node degree $d^i(v)$ of a node $v$ is the maximum size of a set of independent neighbors of $v$. Denote by $\Delta^i(G) = \max \{d^i(v) \mid v \in V\}$. Obviously $\Delta^i(G) \le \alpha(G)$, where $\alpha(G)$ is the independence number of $G$.

Examples: $\Delta^i(G)=1$ for complete graphs. $\Delta^i(G)\le 5$ for unit disc graphs. $\Delta^i(G)=n-1$ for a star graph with $n$ nodes.

My questions:

• What natural graph classes have $\Delta^i(G)\in O(1)$?
• What is known about the distribution of $d^i(v)$ in random graphs?
• For dense graphs the expected value of the independent node degree should be small. Are there any quantitative results? E.g. relating $m/n$ with $\Delta^i(G)$?

Answer 1

Concerning the third question, triangle-free graphs have $\Delta^i(G) = \Delta(G)$. From Turán's theorem, we know that the maximum number of edges on a triangle-free graph is $\big\lfloor\frac{n}{4}\big\rfloor$, and this bound is tight for the complete bipartite graph $K_{n/2,n/2}$. Hence, at least in this case, you can have a dense graph with a large independent node degree, namely $d^i(v) = \frac{n}{2}$ for all $v$.

Answer 2

Answer to your first question.

Proper(Unit) Interval graphs have independent node degree of 2.

Answer 3

Another answer to the first question: Line graphs form another natural class of independent node degree 2. More general, claw-free graphs if they are natural enough for you.