7
$\begingroup$

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)$?
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Richerby Feb 5 '14 at 10:25
  • 1
    $\begingroup$ I am curious: why is it interesting to know that a class has bounded independent node degree? $\endgroup$ – user13136 Feb 7 '14 at 15:55
  • $\begingroup$ 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. $\endgroup$ – Volker Turau Feb 7 '14 at 19:41
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Answer to your first question.

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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