<p>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.</p>

CC BY-SA 3.0
2014-02-07T15:48:35.833Z
2014-02-07T15:48:35.833Z
user13136
<p>Answer to your first question.</p>

<p>Proper(Unit) Interval graphs have independent node degree of 2.</p>

CC BY-SA 3.0
2014-02-07T04:05:26.557Z
2014-02-07T04:05:26.557Z
Dibyayan
<p>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$.</p>

CC BY-SA 3.0
2014-02-04T20:23:23.130Z
2014-02-04T20:23:23.130Z
Vinicius dos Santos
<p>Let $G=(V,E)$ be an undirected graph. The <strong>independent node degree</strong> $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$. </p>

<p>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.</p>

<p>My questions:</p>

<ul>
<li>What natural graph classes have $\Delta^i(G)\in O(1)$?</li>
<li>What is known about the distribution of $d^i(v)$ in random graphs?</li>
<li>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)$?</li>
</ul>

CC BY-SA 3.0
2014-02-05T10:25:17.313Z
Of course, graph theory is highly relevant to computer science but there doesn't seem to be any actual CS content in this question. Wouldn't you get better answers on one of the maths SEs?
David Richerby
CC BY-SA 3.0
2014-02-07T15:55:50.437Z
I am curious: why is it interesting to know that a class has bounded independent node degree?
user13136
CC BY-SA 3.0
2014-02-07T19:41:50.777Z
I have developed a distributed algorithm and its time complexity depends on $\Delta^i(G)$. For classes of graphs with bounded independent node degree this algorithm performs well.
Volker Turau
<graph-theory><randomness><random-graphs>
Independent Node Degree in Undirected Graphs
Volker Turau
# Independent Node Degree in Undirected Graphs

(Asked by: username_0 on 2014-02-04)

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)$?

**Tags:** graph-theory, randomness, random-graphs

> **Comments:**
> **username_1**: Of course, graph theory is highly relevant to computer science but there doesn't seem to be any actual CS content in this question. Wouldn't you get better answers on one of the maths SEs?  
> **username_2**: I am curious: why is it interesting to know that a class has bounded independent node degree?  
> **username_0**: I have developed a distributed algorithm and its time complexity depends on $\Delta^i(G)$. For classes of graphs with bounded independent node degree this algorithm performs well.  

---

## 3 answers

### Answer by username_2 on 2014-02-07. Score: 2

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.


---

### Answer by username_3 on 2014-02-07. Score: 2

Answer to your first question.

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


---

### Answer by username_4 on 2014-02-04. Score: 2

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$.


---

