Characterizations of $k$-Ctrees and Graph Valued Functions

Abstract

We introduce $k$-ctrees, which are a natural generalization of trees. A $k$-ctree can be constructed by recursion as follows: Any set of $k$ independent vertices is a $k$-ctree, and a $k$-ctree of order $n+1$ is obtained by inserting an $(n+1)$-th vertex, and joining it to each of any $k$ independent vertices in a $k$-ctree of order $n$. We obtain basic properties and characterizations of $k$-ctrees involving $k$-degeneracy, triangle-free properties, and number of edges. Further, we determine the conditions under which $k$-ctrees are line, middle, or total graphs. Finally, we pose some open problems, all of them related to the characterization of $k$-ctrees.