Characterizations for Some Types of DNA Graphs

摘要

Vertex induced subgraphs of directed de Bruijn graphs with labels of fixed length k and over α letter alphabet are (α,k)-labelled. DNA graphs are (4,k)-labelled graphs. Pendavingh et al. proved that it is NP-hard to determine the smallest value α k (D) for which a directed graph D can be (α k (D),k)-labelled for any fixed $k geqslant 3$ . In this paper, we obtain the following formulas: $alpha_k(C_n)=lceilsqrt[k-1]{n}rceil$ and $alpha_k(P_n)=lceilsqrt[k-1]{n+1}rceil$ for cycle C n and path P n . Accordingly, we show that both cycles and paths are DNA graphs. Next we prove that rooted trees and self-adjoint digraphs admit a (Δ,k)-labelling for some positive integer k and they are DNA graphs if and only if Δ ≤ 4, where Δ is the maximum number in all out-degrees and in-degrees of such digraphs.