Characterizations of \(k\)-Ctrees and Graph Valued Functions

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.