A new characterization of k-trees and some applications

Abstract

We present a new characterization of k-trees based on their reduced clique graphs and $(k+1)$-line graphs, which are block graphs. We explore structural properties of these two classes, showing that the number of clique trees of a k-tree G equals the number of spanning trees of the $(k+1)$-line graph of G. This relationship allow us to present a new approach for determining the number of spanning trees of any connected block graph and to address a special case of a “reverse problem" raised in the literature. We show that these results can be accomplished in linear time complexity.

1 Introduction

The class of k-trees, introduced in 1968 by Beineke and Pippert (1969), has an inductive definition which naturally extends the definition of a tree. It is a subclass of chordal graphs and it has been the subject of considerable research. In this paper we present new results about this class. First, we prove a new characterization of k-trees, based on two different associated structures: the reduced clique graph, notion introduced by Galinier et al. in Galinier et al. (1995), and the k-line graph, the generalization of the line graph operation introduced by Lê 1993. Despite having been introduced in the mid-1990 s and extensively studied since then, as far as we know, no relationship between these two structures has yet been established.

A clique tree representation of a chordal graph is particularly useful, allowing the development of efficient algorithms that take advantage of the compactness of the representation. In Ho and Lee (1989), an algorithm that generates any clique tree of a chordal graph G is presented, based upon the assumption that the sets of maximal cliques and minimal vertex separators of G are given. From this result, the authors derive an exact formula of counting the number of clique trees of a labeled connected chordal graph. In our paper, we resume the formula, showing that it can be simplified for k-trees.

The number of spanning trees of a connected graph is a well known invariant provided by the Kirchhoff’s Matrix Tree Theorem (Biggs 1993) that can be computed in polynomial time as any cofactor of the Laplacian matrix of the graph. We show that if G is a k-tree, then the number of clique trees of G equals the number of spanning trees of the $(k+1)$-line graph of G, which is a block graph as proved in Oliveira et al. (2021). This result allows us to present a new approach for determining the number of spanning trees of any connected block graph, by establishing a closed formula for it. These results are computed in linear time complexity.

Our results establish interesting relationships on different types of structures, which until now had not been noticed; we believe that these relationships have the potential to improve knowledge about chordal graphs in general and block and k-tree graphs in particular. As an example, we address a reverse problem raised in literature by De Caria and Gutierrez (2012).

2 Basic concepts

Let $G =(V,E)$, be a graph, where $|V|=n$ and $|E| = m$. The set of neighbors of a vertex $v \in V$ is denoted by $N(v) = \{ w \in V; \{v,w\} \in E\}$. The degree of a vertex $v\in V$ is $d(v)=|N(v) |$. For any $S \subseteq V$, the subgraph of G induced by S is denoted G[S]. If G[S] is a complete graph then S is a clique in G. A graph is said to be H-free if it contains no H as an induced subgraph. A vertex $v\in V$ is said to be simplicial in G when N(v) is a clique in G.

Basic concepts about chordal graphs are assumed to be known and can be found in Blair and Peyton (1993) and Golumbic (2004). In this section, the most pertinent concepts are reviewed.

A subset $S \subset V$ is a separator of G if at least two vertices in the same connected component of G are in two distinct connected components of $G[V{\setminus } S]$.

Let $G = (V, E)$ be a chordal graph and $u,v \in V$. A subset $S \subset V$ is a vertex separator for non-adjacent vertices u and v (a uv-separator) if the removal of S from the graph separates u and v into distinct connected components. If no proper subset of S is a uv-separator then S is a minimal uv-separator. When the pair of vertices remains unspecified, we refer to S as a minimal vertex separator (mvs). The set of minimal vertex separators is denoted by $\mathbb {S}$.

The clique-intersection graph of a chordal graph G is the connected weighted graph whose vertices are the maximal cliques of G and whose edges connect vertices corresponding to non-disjoint maximal cliques. Each edge is assigned an integer weight, given by the cardinality of the intersection between the maximal cliques represented by its endpoints. Every maximum weight spanning tree of the clique-intersection graph of G is called a clique tree of G. The set of maximal cliques of G is denoted by $\mathbb {Q}$. A simplicial clique is a maximal clique containing at least one simplicial vertex.

For a chordal graph G and a clique tree T of G, a set $S\subset V$ is a mvs of G if and only if $S= Q\cap Q'$ for some edge $\{Q, Q'\}$ in T. Moreover, the multiset ${\mathbb {M}}$ of the minimal vertex separators of G is the same for every clique tree of G. The multiplicity of the minimal vertex separator S, denoted by $\mu (S)$, is the number of times that S appears in ${\mathbb {M}}$. The determination of the minimal vertex separators and their multiplicities can be performed in linear time (Markenzon and Da Costa Pereira 2010).

The maximal cliques Q and $Q^{\prime }$ of G form a separating pair if $Q \cap Q^{\prime } \ne \emptyset$ and every path in G from a vertex of $Q\backslash Q^{\prime }$ to a vertex of $Q^{\prime } \backslash Q$ contains a vertex of $Q \cap Q^{\prime }$. The reduced clique graph $C_{r}(G)$ of G, introduced by Galinier et al. in Galinier et al. (1995), is the graph whose vertices are maximal cliques of G and whose edges $\{Q,Q^{\prime }\}$ are between cliques Q and $Q^{\prime }$ forming separating pairs.

Theorem 1

(Habib and Stacho 2012) A set S is a minimal vertex separator of a chordal graph G if and only if there exist maximal cliques Q and $Q^{\prime }$ of G forming a separating pair such that $S=Q \cap Q^{\prime }$.

Theorem 2

(Galinier et al. 1995) Let G be a connected chordal graph. A tree T is a clique tree of G if and only if T is a maximum weight spanning tree of $C_r(G)$ where the weight of each edge $\{Q,Q'\}$ is defined as $|Q\cap Q'|$. Moreover, the reduced clique graph $C_r(G)$ is precisely the union of all clique trees of G.

As Theorem 2 states, not all spanning trees of $C_r(G)$ are clique trees of G. In Fig. 1, for example, the maximal cliques of graph G are $Q_1=\{a,b,e\}$, $Q_2=\{b,c,e\}$, $Q_3=\{c,d,e\}$ and $Q_4=\{e,f,g\}$, which are vertices of its reduced clique graph, $C_r(G)$. The edges of $C_r(G)$ are $\{Q_1, Q_2\}$, $\{Q_1, Q_4\}$, $\{Q_2, Q_3\}$, $\{Q_2, Q_4\}$ and $\{Q_3, Q_4\}$, since the cliques in each of these sets form a separating pair. Notice that the tree T is a spanning tree of $C_r(G)$ but T is not a clique tree of G.

Fig. 1

G, $C_r(G)$ and a spanning tree T of $C_r(G)$

The generalization of the line graph operation which we apply in our work is the one introduced by Lê in Lê (1993): for an integer $k\ge 2$, the k-line graph of G, denoted by $\ell _k(G)$, is the graph whose vertices are the k-cliques in G and where two distinct such vertices are adjacent if and only if they have, in G, $k-1$ vertices in common.

3 A new characterization of k-trees

A k-tree is a chordal graph that can be recursively defined as follows. The complete graph with $k+1$ vertices is a k-tree. A k-tree with $n+1$ vertices $(n\ge k+1)$ can be constructed from a k-tree with n vertices by adding a vertex adjacent to all vertices of a k-clique C of the existing k-tree, and only to these vertices. Theorem 3 and Corollary 4 are characterizations of k-trees.

Theorem 3

(Rose 1974) A chordal graph $G = (V, E)$ is a k-tree if and only if

• 1. G is connected,

• 2. G has a k-clique but no $k + 2$ clique,

• 3. every minimal vertex separator of G is a k-clique.

Corollary 4

Let G be a chordal graph, $\mathbb {Q}$ the set of its maximal cliques and $\mathbb {S}$ the set of its minimal vertex separators. Graph G is a k-tree if and only if $|Q|=k+1$, for all $Q \in \mathbb {Q}$, and $|S|=k$, for all $S \in \mathbb {S}$.

In Harary (1969), it is proved that a graph is the line graph of a tree if and only if it is a connected block graph which is $K_{1,3}$-free. In Oliveira et al. (2021), the graphs that are $(k+1)$-line graphs of general k-trees are characterized. Next theorem merges both results.

Theorem 5

(Oliveira et al. 2021) Let $k\ge 1$ be an integer. A graph is the $(k+1)$-line graph of a k-tree if and only if it is a connected block graph which is $K_{1,k+2}$-free.

In the next theorem we characterize k-trees in terms of its reduced clique graph and its $(k+1)$-line graph.

Theorem 6

Let G be a connected chordal graph. Graph G is a k-tree if and only if $C_r(G)$ and $\ell _{k+1}(G)$ are equal.

Proof

Let G be a connected chordal graph. First, suppose that G is a k-tree. By Theorem 3, all maximal cliques of G have cardinality $k+1$; by definition, these cliques are the vertices of $C_r(G)$. There are no cliques of cardinality $(k+2)$ in G (still by Theorem 3); so these maximal cliques are also the vertices of $\ell _{k+1}(G)$. The edges of $C_r(G)$ correspond to minimal vertex separators of G (Theorem 2). Since G is a k-tree, its minimal vertex separators are cliques of cardinality k. All pairs of maximal cliques Q and $Q'$ such that $|Q \cap Q'| = k$ form a separating pair of G and the edge $\{Q,Q'\}$ belongs to $C_r(G)$. These edges are precisely the edges of $\ell _{k+1}(G)$.

Conversely, suppose that G is not a k-tree. Then, by Theorem 3, two cases can occur.

Case A: G has at least one clique Q of cardinality $k+2$. Suppose that Q is a maximal clique. In this case, all $k+2$ subcliques of Q with cardinality $k+1$ belong to the set of vertices of $\ell _{k+1}(G)$ with their intersections of cardinality k. However, as these cliques are not maximal cliques they do not appear in $C_r(G)$. So $C_r(G)$ is not equal to $\ell _{k+1}(G)$. Contradiction.

Case B: there is a mvs in G with cardinality not equal to k. In this case there is an edge belonging to $C_r(G)$ that does not appear in $\ell _{k+1}(G)$. Contradiction. $\square$

Notice that, by Theorem 5, the reduced clique graph of a k-tree is a block graph, a fact that is not true for chordal graphs in general as we can see in Fig. 1.

It is interesting to observe that, recently, Che (2023) has also worked with the $(k+1)$-line graph of a k-tree to study different parameters as Wiener index and Szeged index for k-trees and block graphs. He defines a new structure, particular to k-trees, called the k-clique graph of G (denoted G/[k]) and proves that if G is a k-tree then the block graph of G/[k] is isomorphic to $\ell _{k+1}(G)$.

Theorems 7 and 8 show properties of $C_r(G)$, where G is a k-tree. They emphasize the strong relation between the structural features of the graphs.

Theorem 7

Let G be a k-tree, $\mathbb {S}$ its set of minimal vertex separators and $C_r(G)$ its reduced clique graph. Then each maximal clique Q of $C_r(G)$ corresponds to a minimal vertex separator $S \in \mathbb {S}$, and moreover, the multiplicity of the mvs S in G equals $|Q| -1$.

Proof

Let G be a k-tree. Each maximal clique Q of $C_r(G)$ is a block whose vertices represent the maximal cliques of G that share the same msv S. Then, no other edge of $C_r(G)$ corresponds to S, since no other maximal clique of G contains S. As each edge of the block Q is associated with S, it will appear $|Q|-1$ times in any clique tree. Hence, $\mu (S)=|Q|-1$. $\square$

Theorem 8

Every connected block graph is the reduced clique graph of some k-tree.

Proof

Let H be a connected block graph with n vertices. So, there exists an integer $p\ge 0$ such that H is $K_{1,p+2}$-free. If $p\ge 1$, then consider $k=p$. By Theorem 5, H is the $(k+1)$-line graph of a k-tree, say G, whence, by Theorem 6, H is also the reduced clique graph of G. If $p=0$, then H is a complete graph $K_n$ and, for all $k\ge 2$, it is the $(k+1)$-line graph of the k-star (a k-tree with $|{\mathbb {S}}| \le 1$) with $n+k$ vertices. $\square$

4 The number of clique trees of a k-tree

In this section two interesting applications of the previous results are presented: the determination of the number of clique trees of a k-tree and, as an immediate consequence, the determination of the number of spanning trees of a block graph.

In 1989, Ho and Lee (1989) presented a formula for counting the number of clique trees of a chordal graph. Kumar and Madhavan (2002) modified this formula, focusing in minimal vertex separators and stating that the complexity time of the process is $|{\mathbb {S}}| (\omega (G)|V| +|E|)$, where $\omega (G)$ is the clique number of G. We resume the formula presented in Ho and Lee (1989), showing that for k-trees it can be simplified and its time complexity reduced. To enunciate the result of Ho and Lee (1989), some definitions are needed.

Let $G=(V,E)$ be a chordal graph, $\mathbb {Q}$ the set of its maximal cliques and $\mathbb {S}$ the set of its minimal vertex separators. For a set $A \subset V$, $Adj(A) = \cup _{v\in A} N(v) {\setminus } A$. For every minimal vertex separator $S \in {\mathbb {S}}$,

$${\mathfrak C}_S = \{ C \,|\, C \ \text{ is } \text{ a } \text{ connected } \text{ component } \text{ of } \ G{\setminus } S \text{ and } Adj(C) = S\}$$

and for every $C \in {\mathfrak C}_S$,

$${\mathbb {Q}}_C = \{Q \in {\mathbb {Q}} \,|\, Q \ \text{ is } \text{ in } \ G[C\cup S] \text{ and } S\subset Q\}.$$

Theorem 9

(Ho and Lee (1989)) The number of clique trees of a connected chordal graph G is equal to

$$\begin{aligned} \prod _{S \in {\mathbb {S}}} \left[ \left( \sum _{C \in {\mathfrak C}_S} |{\mathbb {Q}}_C|\right) ^ {|{\mathfrak C}_S| -2} \cdot \prod _{C \in {\mathfrak C}_S} |{\mathbb {Q}}_C| \right] , \end{aligned}$$

(1)

where $\mathbb {S}$ is the set of minimal vertex separators of G.

Actually, the determination of the number of clique trees of k-trees depends only on the multiplicity $\mu (S)$ of each mvs S, as seen in Theorem 10.

Theorem 10

The number of clique trees in a k-tree G is equal to

$$\begin{aligned} \prod _{S \in {\mathbb {S}}} \left( \mu (S) +1 \right) ^{\mu (S)-1}, \end{aligned}$$

(2)

where $\mathbb {S}$ is the set of minimal vertex separators of G.

Proof

Let G be a k-tree. We are going to apply to G Equation (1). It is known that $|S|=k$ for all $S\in {\mathbb {S}}$ and $|Q|=k+1$ for all $Q\in {\mathbb {Q}}$ (Corollary 4). Let $S \in {\mathbb {S}}$ and $C \in {\mathfrak C}_S$.

Let us observe $C_r(G)$. The removal of a mvs S corresponds, by Theorem 7, to the removal of the edges of a maximal clique (a block) of $C_r(G)$. The vertices that are endpoints of these edges correspond to maximal cliques of G containing S. We can consider two types of remaining vertices in $C_r(G)$: isolated vertices or vertices that were separators in the original $C_r(G)$. Either one corresponds to a component in $G[V{\setminus } S]$ and these vertices are the only ones in each component that contains S. Therefore $|{\mathbb {Q}}_C|=1$ and the second factor of Equation (1) is equal to 1.

The first factor of Equation (1) is now $\left( \sum _{C \in {\mathfrak C}_S} 1\right) ^ {|{\mathfrak C}_S| -2}$. To consider all $C \in {\mathfrak C}_S$ is equivalent to consider the number of components of $G[V{\setminus } S]$. It was seen that, in $C_r(G)$, each vertex containing S establishes a component. These vertices form a block (that is, a maximal clique of $C_r(G)$) and, by Theorem 7, we know that $|Q| -1 =\mu (S)$. So, the factor becomes $\left( \sum _{\mu (S)+1} 1\right) ^ {\mu (S)-1}$. $\square$

Theorem 11

The determination of the number of clique trees of a k-tree can be performed in linear time complexity.

Proof

The determination of the minimal vertex separators and their multiplicities can be performed in O(m) (Markenzon and Da Costa Pereira 2010). The number of maximal cliques of a k-tree G with n vertices is $n-k$. Then any clique tree of G has $n-k-1$ edges, each one of them corresponding to a minimal vertex separator of $\mathbb {M}$. So, $\sum _{S \in \mathbb {S}} \mu (S) = n-k-1$.

Each factor of Equation (2) is $\left( \mu (S) +1 \right) ^{\mu (S)-1}$. So, it corresponds to a product of $\mu (S_i)-1$ times the value $\mu (S_i) +1$; each factor has $\mu (S_i)- 1$ factors. Hence, the total number of factors is less than $\sum _{S\in {\mathbb {S}}} \mu (S)$, that, as it was seen, is less than n. Hence, the computation of Equation (2) has linear time complexity. $\square$

A spanning tree of a connected graph G is a subgraph of G that is a tree and contains all vertices of G. The number of spanning trees of G, $\tau (G)$, is a well known invariant of the literature, provided by the Kirchhoff’s Matrix Tree Theorem (Biggs 1993). This is a very interesting result, since it combines structural and spectral aspects of the graph. The Laplacian matrix of a graph G with n vertices is the matrix $\textbf{L}(G)=\textbf{D}(G)-\textbf{A}(G)$, where $\textbf{A}(G)$ and $\textbf{D}(G)$ are the adjacency matrix and the diagonal matrix of the vertex degrees of G, respectively. The Laplacian eigenvalues of G, $\mu _1 \ge \mu _2 \ge ...\ge \mu _{n}=0$, are the eigenvalues of $\textbf{L}(G)$. As a consequence of Kirchhoff’s Matrix Tree Theorem, the number of spanning trees of G can be expressed by its Laplacian eigenvalues as $\tau (G)=\frac{1}{n} \prod _{i=1}^{n-1} \mu _i$.

Theorem 12 shows how clique trees of a k-tree are related to the spanning trees of a block graph and Corollary 13 presents a closed formula for the number of spanning trees of a connected block graph.

Theorem 12

If G is a k-tree, then the set of clique trees of G equals the set of spanning trees of $C_r(G)$.

Proof

Let G be a k-tree. By Corollary 4, all minimal vertex separators of a k-tree have cardinality k, so all edges of $C_r(G)$ have the same weight, k. Thus, all spanning trees of $C_r(G)$ have the same weight and therefore they are all maximum-weight spanning trees. So by Theorem 2, a tree T is a clique tree of G if and only if T is a spanning tree of $C_r(G)$. $\square$

The number of spanning trees of a connected block graph can be calculated by several different ways. For example, in Abiad et al. (2017) Theorem 4, the authors apply algebraic techniques for calculating $\tau (G)$ for G being a connected block graph with all the blocks of same size. Here we consider G a general connected block graph G and obtain $\tau (G)$ as a consequence of our previous results.

Corollary 13

Let G be a connected block graph and $\mathbb {Q}$ its set of maximal cliques. The number of spanning trees of G is

$$\begin{aligned} \tau (G) = \prod _{Q \in {\mathbb {Q}}} \left( |Q| \right) ^{|Q|-2}. \end{aligned}$$

(3)

The efficiency of the determination of the number of spanning trees of a connected block graph is proved in Theorem 15. It relies on a compact representation of chordal graphs, presented in Markenzon et al. (2013). Based on this representation, it was possible to state the next theorem.

Theorem 14

(Markenzon et al. 2013) Let $G=(V,E)$ be a connected chordal graph and $\mathbb {Q}$ its set of maximal cliques. Then

$$ \sum _{Q\in {\mathbb {Q}}} |Q| < n + m.$$

Theorem 15

The determination of the number of spanning trees of a connected block graph can be performed in linear time complexity.

Proof

The determination of the maximal cliques is performed in O(m) complexity time (Markenzon and Da Costa Pereira 2010). Let ${\mathbb {Q}} = Q_1, \ldots Q_{|{\mathbb {Q}|}}$. Each factor of Equation (3) is $(|Q_i|)^{|Q_i|-2}$. So, it corresponds to a product of $|Q_i|-2$ times a constant value, $|Q_i|$; each factor has $|Q_i|-2$ factors. Hence, the total number of factors is less than $\sum _{Q\in {\mathbb {Q}}} |Q|$, that, by Theorem 14, is less than $n+m$. $\square$

Fig. 2

Family $\mathfrak {T}=\{T_1,T_2, T_3\}$ and graph $G_{\mathfrak {T}}$

5 A reverse problem

Perhaps the most well known reverse problem in graphs is the one solved by Havel in 1955 and Hakimi in 1962, the famous Havel-Hakimi algorithm, that answers the following question: “Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list?”

De Caria and Gutierrez (2012) presented, in 2012, a new reverse problem involving, this time, the clique trees of a graph: “Given a family $\mathfrak {T}$ of trees, all having the same vertex set $V_{\mathfrak {T}}$, determine whether there exists a chordal graph G whose set of clique trees equals $\mathfrak {T}$.” Their solution is quite complex, dealing with auxiliary graphs in which seven necessary conditions are established to solve the problem.

We can consider the same problem for k-trees: “Given a family $\mathfrak {T}$ of trees, all having the same vertex set $V_{\mathfrak {T}}$, determine whether there exists a k-tree G whose set of clique trees equals $\mathfrak {T}$." Given the properties stated in this paper it is almost immediate to solve this problem.

Given a family $\mathfrak {T}$ of trees with common set of vertices $V_{\mathfrak {T}}$, let $E_{\mathfrak {T}}$ denote the set of edges each of which is in at least one tree of $\mathfrak {T}$. Let $G_{\mathfrak {T}}=(V_{\mathfrak {T}}, E_{\mathfrak {T}})$. For instance, in Fig. 2, family $\mathfrak {T}=\{T_1,T_2, T_3\}$ and graph $G_{\mathfrak {T}}=(V_{\mathfrak {T}}, E_{\mathfrak {T}})$ are shown.

Fig. 3

Family $\mathfrak {T}=\{T_1, T_2,..., T_9\}$, graph $G_{\mathfrak {T}}$ and 2-tree G

Theorem 16 provides a solution to the reverse problem for k-trees.

Theorem 16

Let $\mathfrak {T}$ be a family of trees, all having the same vertex set $V_{\mathfrak {T}}$. There is a k-tree G such that the set of clique trees of G equals $\mathfrak T$ if and only if the following conditions are satisfied:

• 1. $G_{\mathfrak {T}}=(V_{\mathfrak {T}}, E_{\mathfrak {T}})$ is a connected block graph,

• 2. the number of spanning trees of $G_{\mathfrak {T}}$ is equal to $|\mathfrak {T}|$.

Proof

Let $\mathfrak {T}$ be a family of trees, all having the same vertex set $V_{\mathfrak {T}}$.

Suppose there is a k-tree G such that the set of clique trees of G equals $\mathfrak T$. By definition, graph $G_{\mathfrak {T}}$ is the union of all trees of ${\mathfrak {T}}$, then, by Theorem 2, it is the reduced clique graph of G, $C_r(G)$. Thus, by Theorems 5 and 6, $G_{\mathfrak {T}}$ is a connected block graph. So, condition 1 holds. Furthermore, by Theorem 12, the number of clique trees of G equals the number of spanning trees of $C_r(G)$. Thus, condition 2 is also satisfied.

Conversely, assume that both conditions 1 and 2 are satisfied. So, $G_{\mathfrak {T}}$ is a connected block graph and then, by Theorem 8, there is a k-tree, say G, whose reduced clique graph is $G_{\mathfrak {T}}$. As $|{\mathfrak {T}}|$ equals the number of spanning trees of $G_{\mathfrak {T}}$, by Theorem 12, the set of clique trees of G equals the trees of ${\mathfrak {T}}$. $\square$

Observe that, in Fig. 2, the first condition of Theorem 16 is satisfied, but by Corollary 13, the graph $G_{\mathfrak {T}}$ has $2^0\cdot 4^2=16$ spanning trees. Thus, the set $\mathfrak {T}$ does not solve the reverse problem, that is, $\mathfrak {T}$ is not the set of clique trees of any k-tree.

As for the set $\mathfrak {T}=\{T_1, T_2,..., T_9\}$ in Fig. 3, $G_{\mathfrak {T}}$ is a connected block graph and, by Corollary 13, the number of spanning trees of $G_{\mathfrak {T}}$ is $3^1 \cdot 3^1=9$. Thus, both conditions of Theorem 16 are satisfied. In Fig. 3, we also show a 2-tree G, whose set of clique trees is $\mathfrak {T}$.