04134077

a

04134077 Das, Sajal K. Deo, Narsingh Prasad, Sushil Reverse binary digraphs. Combinatorics, graph theory, and computing, Proc. 20th Southeast Conf., Boca Raton/FL (USA) 1989, Congr. Numerantium 71, 53-66 (1990). 1990 EN dominating set directed graphs digraphs Zbl 0688.00003 [For the entire collection see Zbl 0688.00003.] The paper studies a new family of labeled, directed graphs called reverse binary digraphs, which are generated incrementally in that the subgraph induced by nodes 1,2,...,n in an $(n+1)$-node reverse binary digraph is an n-node reverse binary digraph. It is shown that an n-node reverse binary digraph is acyclic except for the self-loops on the nodes 1 and 2, weakly connected for $n\ge 3$, and nonplanar for $n\ge 15$. It has O(n log n) edges, a longest directed path of length $O(\log\sp* n)$, a maximum clique of size $O(\log\sp* n)$, a smallest dominating set of size O(log n-log log n), and a maximum matching of size O(log n), where $\log\sp* n$ is the smallest k such that $\log\sp{(k)}n\le 1$ with $\log\sp{(k)}n=\log (\log\sp{(k-1)}n)$ and $\log\sp{(0)}n=n$. Wai-Kai Chen