A \(k\)-tree is a graph that can be formed by starting with \(K_{k+1}\) and iterating the operation of making a new vertex adjacent to all the vertices of a \(k\)-clique of the existing graph. A structural characterization of 3-trees with diameter at most 2 is proven. This implies a corollary for planar 3-trees which leads to a description of their degree sequences.
In this paper, we seek a structural (constructive) characterization of 3-trees with diameter at most 2.
A \(k\)-leaf is a degree \(k\) vertex of a \(k\)-tree.
See [5] for a survey of results on \(k\)-trees. There are many results describing and characterizing the structure of \(k\)-trees. Graphs with diameter 2 have been studied in relation to many other graph classes, such as cages and planar graphs [11].
A \(k\)-tree has diameter 1 if and only if it is \(K_{k+1}\). For 2-trees, the following theorem was proved in [6].
1. \(G\) is has diameter at most 2.
2. \(G\) does not contain \(P_{6}^{2}\).
3. \(G\) is \(T+K_{1}\) for any tree \(T\), or any graph formed by adding any number of vertices adjacent to pairs of vertices of \(K_{3}\).
Note that \(1\Leftrightarrow2\) is a forbidden subgraph characterization, while \(1\Leftrightarrow3\) is a structural (constructive) characterization. In [4], Proposition 1.3 was generalized to a structural characterization of maximal 2-degenerate graphs with diameter 2. In [2], a forbidden subgraph characterization was found for \(k\)-trees with diameter \(d\geq2\). Thus the next natural questions are to find a structural characterization of 2-trees with diameter 3 and 3-trees with diameter 2.
Definitions of terms and notation not defined here appear in [3]. In particular, \(n\left(G\right)\) is the number of vertices of a graph \(G\). The neighborhood of a vertex \(v\) is denoted \(N\left(v\right)\), and the closed neighborhood is denoted \(N\left[v\right]\). The square \(G^{2}\) is formed by adding all edges between pairs of vertices with distance 2 in \(G\). The join of graphs \(G\) and \(H\) is denoted \(G+H\).
One way for a \(k\)-tree to have diameter at most 2 is for there to be a vertex adjacent to all other vertices.
The following observations should be immediate.
a. Adding a \(k\)-leaf to \(T\) cannot reduce the diameter.
b. Duplicating a \(k\)-leaf arbitrarily many times will not change the diameter.
Proof. A \(k\)-tree \(G\) has diameter at most 2 if and only if the distance between any two vertices of \(G\) is at most 2. By Lemma 2.2, this will be the case if and only if any two \(k\)-leaves are at distance at most 2. This will hold if and only if any two \(k\)-leaves of \(G\) have a common neighbor. ◻
For order \(n>k+1\), \(k\)-paths are just the \(k\)-trees with exactly two \(k\)-leaves [10]. See Figures 1 and 2 for examples of \(k\)-paths.
Proof. \(\left(\Rightarrow\right)\) Any \(k\)-tree \(T\) has a deletion sequence \(v_{1}\cdots v_{n}\) so that \(d\left(v_{i}\right)=\max\left\{ k,n-i\right\}\) when \(v_{i}\) is deleted. Joining a vertex \(x\) to \(T\) results in a graph \(T'\) with a deletion sequence \(v_{1}\cdots v_{n}x\) so that \(d\left(v_{i}\right)=\max\left\{ k+1,n+1-i\right\}\) when \(v_{i}\) is deleted. Thus \(T'\) is a (\(k+1\))-tree.
\(\left(\Leftarrow\right)\) Let \(T+K_{1}\) have the \(K_{1}\) denoted \(x\). Then \(T+K_{1}\) has a deletion sequence \(v_{1}\cdots v_{n}x\) so that \(d\left(v_{i}\right)=\max\left\{ k+1,n+1-i\right\}\) when \(v_{i}\) is deleted. Thus \(T\) has a deletion sequence \(v_{1}\cdots v_{n}\) so that \(d\left(v_{i}\right)=\max\left\{ k,n-i\right\}\) when \(v_{i}\) is deleted, so \(T\) is a \(k\)-tree.
The proof for \(k\)-paths is essentially the same. ◻
In this section, we characterize 2-trees with diameter at most 3.
A common triple is three vertices \(\left\{ x,y,z\right\}\) that form a triangle of a 2-tree \(T\) so that any 2-leaf of \(T\) is adjacent to at least two of them.
Proof. \(\left(\Leftarrow\right)\) If \(T\) has a dominating triple, then there is a path of length at most 3 between any two vertices of \(T\).
\(\left(\Rightarrow\right)\) Suppose that \(T\) has diameter at most 3. The result is obvious for diameter 1 or 2, so suppose \(T\) has diameter 3.
We use induction on \(n\). Assume the result holds for 2-trees with order \(n\), and let \(T\) have order \(n+1\), and 2-leaf \(v\). Now \(T-v\) has diameter at most 3, so it has a dominating triple \(t=\left\{ x,y,z\right\}\). If \(v\) is adjacent to any of its vertices, \(T\) also has a dominating triple and we are done. Thus we assume that \(T\) has no dominating triple with a vertex adjacent to \(v\).
Deleting two vertices of \(t\) (say \(x\) and \(y\)) will disconnect \(v\) from the third (\(z\)). Thus there is a vertex \(w\) adjacent to \(x\) and \(y\) in the same component of \(T-x-y\) as \(v\). We may assume that \(z\) has no private neighbor \(a\), since else \(d\left(v,a\right)=4\). But then \(\left\{ x,y,w\right\}\) is also a dominating triple. Thus by our assumption, \(v\) is not adjacent to \(w\). Say \(d\left(v,x\right)=2\). Then \(y\) has no private neighbor \(b\), since else \(d\left(v,b\right)=4\). But then \(x\) is a dominating vertex of \(T-v\). Let \(N\left(v\right)=\left\{ u_{1},u_{2}\right\}\). Then \(T\) has a dominating triple \(\left\{ x,u_{1},u_{2}\right\}\). ◻
A fan is \(P_{r}+K_{1}\), where \(P_{r}\) is a path. Call \(K_{1}\) the center of the fan.
Proof. \(\left(\Leftarrow\right)\) If this holds, any vertex of \(T\) is adjacent to a vertex of \(t\).
\(\left(\Rightarrow\right)\) Let \(T\) have a dominating triple \(t=\left\{ x,y,z\right\}\). Let \(v\) be a vertex not in \(t\), so \(v\) is adjacent to a vertex \(x\) of \(t\). If \(v\) is adjacent to two vertices of \(t\), it is contained in a fan centered at \(x\). Else \(v\) is adjacent to \(x\) and a vertex \(u\) not in \(t\). Now \(u\) is adjacent to \(x\), and the argument can be repeated, producing a fan centered at \(x\). ◻
To characterize 3-trees with diameter 2, we use the strategy of starting with a 3-tree with a dominating vertex, and then considering what can be added while maintaining diameter 2.
Thus a 2-fan is just a fan. Any \(k\)-fan is a \(k\)-path, and hence also a \(k\)-tree. Any 3-fan is maximal planar (see Figure 2).
We may be able to identify a triangle of a 3-fan with a triangle of a 3-tree (with the base as one of the identified edges) while maintaining diameter 2. Call this operation fan overlapping. Fan overlapping produces only 3-trees since identifying \(k\)-cliques of two \(k\)-trees produces another \(k\)-tree.
1. \(T=H+K_{1}\), where \(H\) is a 2-tree.
2. Let \(K_{4}\) have vertices \(\left\{ u,x,y,z\right\}\). Then \(T\) is formed by fan overlapping, where the base of the fan must be \(ux\), \(uy\), or \(xy\), and adding 3-leaves with root \(\left\{ x,y,z\right\}\).
3. Let \(uxy\) be the \(K_{3}\) in \(K_{3}+\overline{K}_{r}\), \(r\geq1\). Then \(T\) is formed by fan overlapping, where the base of the fan must be \(ux\), \(uy\), or \(xy\).
Proof. \(\left(\Leftarrow\right)\) Clearly each construction produces a 3-tree. In Case 1, there is a dominating vertex. In Case 2, every pair of vertices not in \(\left\{ u,x,y,z\right\}\) has a neighbor in \(\left\{ u,x,y,z\right\}\). In Case 3, every pair of vertices not in \(\left\{ u,x,y\right\}\) has a neighbor in \(\left\{ u,x,y\right\}\). Thus each 3-tree has diameter at most 2.
\(\left(\Rightarrow\right)\) Assume the hypotheses. Let \(u\) have maximum degree in \(T\), \(S=V\left(T\right)-N\left[u\right]\), and \(H=N\left(u\right)\). Now \(H\) is a 2-tree [7], so \(T-S\) is a 3-tree. Thus if \(u\) is a dominating vertex, \(T-u\) is a 2-tree by Lemma 2.5. Thus we assume \(T\) has no dominating vertex, so \(S\) is nonempty.
Clearly, every vertex in \(S\) neighbors a vertex in \(H\). Let \(R\) be all vertices in \(H\) with neighbors in \(S\). Every vertex in \(R\) is contained in a triangle of \(H\), and each pair of these triangles must have a have a nonempty intersection, since else two vertices of \(S\) have no common neighbor. Then \(R\) is a union of triangles, and the graph induced by \(R\) has diameter 2. It is contained in a minimal 2-tree \(T'\) which has diameter 2, so by Proposition 1.3, \(T'\) has a dominating vertex or a common triple.
Suppose \(T'\) has a dominating vertex \(x\). Now \(H\) must have diameter 2, since else some vertex in \(S\) would be more than 2 away from a vertex in \(H\). If \(x\) is dominating in \(H\), \(x\) is also dominating in \(T\). By assumption, we can exclude this case. Thus \(H\) has a common triple, so \(T'\) does also.
Next we assume that \(T'=K_{3}\), whose vertices are \(\left\{ x,y,z\right\}\), none of which is dominating in \(H\). There is at least one vertex \(v\) in \(S\) whose neighbors are \(T'\). Then any other vertex in \(H\) is adjacent to a vertex in \(T'\) and \(u\). Then \(T\) is formed by fan overlapping with bases \(ux\), \(uy\), or \(xy\), and adding at least one 3-leaf with root \(\left\{ x,y,z\right\}\).
Next we assume that \(T'=K_{2}+\overline{K}_{s}\), the vertices of \(K_{2}\) are \(\left\{ x,y\right\}\), neither of which is dominating in \(H\). Then for each vertex \(w\) in the \(\overline{K}_{s}\), there is at least one vertex in \(S\) not adjacent to it (else we return to the previous case). Then every vertex of \(T\) not in \(D=\left\{ u,x,y\right\}\) is adjacent to at least two vertices in \(D\). Thus every vertex not in \(D\) is part of a 3-fan with base \(ux\), \(uy\), or \(xy\), and there is at least one vertex of \(T\) adjacent to all vertices of \(D\).
Finally, we assume \(T'\) contains a triangle \(xyz\), any other vertex of \(T'\) is adjacent to exactly two of \(\left\{ x,y,z\right\}\), and each pair (\(xy\), \(xz\), and \(yz\)) has at least one additional neighbor in \(T'\). Now each vertex of \(T'\) is adjacent to at least one vertex in \(S\), so \(H=T'\). Thus each vertex in \(S\) is adjacent to at least two vertices in \(\left\{ x,y,z\right\}\). Thus each vertex in \(T\) is adjacent to at least two vertices in \(\left\{ x,y,z\right\}\). But then we can return to the previous case by giving \(\left\{ x,y,z\right\}\) the roles of \(\left\{ u,x,y\right\}\). ◻
This characterization allows us to evaluate or bound parameters of 3-trees with diameter 2. In the following results, we refer to the three graph classes in the statement of Theorem 4.2 as Cases 1, 2, and 3.
Proof. In Case 1, a 3-tree with a dominating vertex has \(\Delta=n-1\), so \(n=\Delta+1\).
In Case 2, for each vertex \(v\in\left\{ u,x,y,z\right\}\), let \(S_{v}\) be the set of vertices not adjacent to \(v\). To have \(\Delta\left(T\right)=n-1-r\), each \(S_{v}\) must contain at least \(r\) vertices. Now vertices in \(S_{u}\) are adjacent to triangle \(xyz\), so they are only in \(S_{u}\).
The vertices in \(S_{x}\) may be in \(S_{y}\) or \(S_{z}\) (not both), and similarly for the vertices in \(S_{y}\) or \(S_{z}\). However, there must be at least one vertex only in one of the sets \(S_{x}\), \(S_{y}\), or \(S_{z}\). If there is exactly one vertex adjacent to (say) \(\left\{ u,y,z\right\}\), then \(\Delta\left(T\right)=n-1-r\) requires at least \(r\) vertices each in \(S_{y}\) and \(S_{z}\), and none in both. Thus \(n\geq4+3r+1=3r+5\) and \(\Delta\left(T\right)\geq n-1-\frac{n-5}{3}=\frac{2}{3}n+\frac{2}{3}\), so \(n\leq\frac{3\Delta-2}{2}\).
Suppose there are two vertices in only one of the sets \(S_{x}\), \(S_{y}\), or \(S_{z}\), say one each in sets \(S_{x}\) and \(S_{y}\). Any other vertex can be in any two of the three sets. Then \(s\) vertices in \(S_{x}\cup S_{y}\cup S_{z}\) yield \(\left|S_{x}\right|\cup\left|S_{y}\right|\cup\left|S_{z}\right|\leq2s-2\), so \(r\leq\frac{2s-2}{3}\). Now \(n=4+s+r\geq4+\frac{3r+2}{2}+r=\frac{5r+10}{2}\), so \(r\leq\frac{2n-10}{5}\). Then \(\Delta\left(T\right)\geq n-1-\frac{2n-10}{5}=\frac{3n}{5}+1\). Thus \(n\leq\frac{5\Delta-5}{3}\).
In Case 3, \(K_{3}+\overline{K}_{r}\) has \(r\geq1\), with \(uxy\) being the \(K_{3}\). There are at most \(n-4\) vertices with exactly two neighbors in \(K_{3}+\overline{K}_{r}\). These vertices split into three sets based on which of \(\left\{ u,x,y\right\}\) they are not adjacent to. When \(\Delta\) is minimum, one of these sets contains at least \(\frac{n-4}{3}\) vertices. Then \(\Delta\geq n-1-\frac{n-4}{3}=\frac{2n+1}{3}\), so \(n\leq\frac{3\Delta-1}{2}\). ◻
The smallest possible \(\Delta\) for a 3-tree with diameter 2 and order \(n\) is \(n-1\) for \(3\leq n\leq7\) and \(\left\lceil \frac{3n}{5}+1\right\rceil\) for \(n\geq5\).
Next we consider an important special class of \(k\)-trees.
A plane drawing of a graph is a drawing in the plane that has no crossings. A graph is outerplanar if it has a plane drawing with all vertices on the boundary of the exterior region. A graph is a maximal outerplanar graph (MOP) if no edge can be added so that the resulting graph is still outerplanar.
An Apollonian network is a planar 3-tree.
The MOPs are exactly the simple 2-trees, and the planar 3-trees are exactly the simple 3-trees [10]. See Figures 1 and 2 for examples of these graphs.
1. \(T=H+K_{1}\), where \(H\) is a MOP.
2. Let \(K_{4}\) have vertices \(\left\{ u,x,y,z\right\}\). Then \(T\) is formed by fan overlapping with bases \(ux\), \(uy\), \(uz\), and only triangles of \(K_{4}\) are used for overlapping, each at most once. A single 3-leaf may be added with root \(\left\{ x,y,z\right\}\).
3. Let \(uxy\) be the \(K_{3}\) in \(K_{3}+\overline{K}_{r}\), \(1\leq r\leq2\). Then \(T\) is formed by fan overlapping with bases \(ux\), \(uy\), or \(xy\). Only triangles of \(K_{3}+\overline{K}_{r}\) are used for overlapping, and each at most once.
Proof. In Case 1, for \(T\) to be planar, \(H\) must be outerplanar.
In Cases 2 and 3, for \(T\) to be planar, it must be a simple 3-tree, so each root is used at most once. Thus each triangle of \(K_{4}\) or \(K_{3}+\overline{K}_{r}\) can be used at most once for overlapping, and no other triangle can be used for overlapping. In Case 3, \(r\leq2\), since \(K_{3}+\overline{K}_{3}\) is not planar. ◻
Seyffarth [11] studied maximal planar graphs with diameter 2. Seyffarth showed that such graphs have \(n\leq\frac{3}{2}\Delta+1\) and found two infinite classes of maximal planar graphs that show this bound is sharp. This is not claimed to be a complete characterization.
Of course, maximal planar graphs with diameter 2 need not be 3-trees. For example, the double wheel \(\overline{K}_{2}+C_{n-2}\) has minimum degree 4 and diameter 2. Seyffarth’s two classes both contain subgraphs with minimum degree 4. Thus it appears that the bound on \(n\) can be improved when we only consider planar 3-trees.
Proof. In Case 1, a 3-tree with a dominating vertex has \(\Delta=n-1\), so \(n=\Delta+1\).
In Case 2, there can only be one vertex not adjacent to \(u\), so \(\Delta\geq n-2\), and \(n\leq\Delta+2\).
In Case 3, \(K_{3}+\overline{K}_{r}\) has \(1\leq r\leq2\), with \(uxy\) being the \(K_{3}\). There are at most \(n-4\) vertices with exactly two neighbors in \(K_{3}+\overline{K}_{r}\). These vertices split into three sets based on which of \(\left\{ u,x,y\right\}\) they are not adjacent to. When \(\Delta\) is minimum, one of these sets contains at least \(\frac{n-4}{3}\) vertices. Then \(\Delta\geq n-1-\frac{n-4}{3}=\frac{2n+1}{3}\), so \(n\leq\frac{3\Delta-1}{2}\). ◻
Thus no planar 3-tree can be an extremal graph for Seyffarth’s theorem.
We may be interested to characterize the degree sequences of planar 3-trees with diameter 2. Note that in Case 1, \(G\) has a dominating vertex \(u\) if and only if \(G-u\) is a MOP. Consequently, we can determine whether a list of numbers is a degree sequence of a planar 3-tree with a dominating vertex if and only if we can determine whether a corresponding list is the degree sequence of a MOP. However, no characterization of degree sequences of MOPs is known. See [1,8,9] for partial results. Thus we instead consider graphs for Cases 2 and 3 that are not covered by Case 1.
Case 2: To avoid a dominating vertex, we assume there is a vertex rooted on each triangle of the \(K_{4}\) with vertex set \(\left\{ u,x,y,z\right\}\). We designate the six triangles A-F in order around \(u\) (see the graph above). We can break down the cases by how many vertices are in each of the 6 triangles. Note that if there are no vertices in \(D\), we can move the vertices in \(C\) to \(B\) without changing the degree sequence.
We organize cases based on how many degree 5 vertices there are rooted on the \(K_{4}\). We can reduce the cases to possibly adding vertices inside ACE, ABD, ABCD, or ABCDEF. Suppose \(a\) vertices are added inside A, and similarly for the other triangles. We require \(a,b\geq1\) when A and B are both listed in a case, and similarly for the pairs \(\left\{ C,D\right\}\) and \(\left\{ E,F\right\}\), but not otherwise. We obtain the following possible degree sequences (\(d^{r}\) indicates \(r\) vertices of degree \(d\)).
Case 3: To avoid a dominating vertex, there must be fans attached to at least one of each of the three pairs \(\left\{ A,D\right\}\), \(\left\{ B,E\right\}\), and \(\left\{ C,F\right\}\) (see the graph above). Thus the triangles where fans are attached are (up to symmetry) ABC, ABF, ABCD, ABDF, ABCDE, or ABCDEF. Suppose \(a\geq1\) vertices are added inside A, and similarly for the other triangles. We obtain the following possible degree sequences.
| Triangles | Degree Sequence |
| ABC | \(\left(4+a+b\right)^1\left(4+a+c\right)^1\left(4+b+c\right)^16^14^a+b+c-33^4\) |
| ABF | \(\left(4+a+b\right)^1\left(4+a+f\right)^1\left(4+b+f\right)^15^14^a+b+f-23^3\) |
| ABCD | \(\left(4+a+b+d\right)^1\left(4+a+c+d\right)^1\left(4+b+c\right)^16^14^a+b+c+d-33^4\) |
| ABDF | \(\left(4+a+b+d\right)^1\left(4+a+d+f\right)^1\left(4+b+f\right)^15^24^a+b+d+f-43^4\) |
| ABCDE | \(\left(4+a+b+d+e\right)^1\left(4+a+c+d\right)^1\left(4+b+c+e\right)^16^15^14^a+b+c+d+e-53^5\) |
| ABCDEF | \(\left(4+a+b+d+e\right)^1\left(4+a+c+d+f\right)^1\left(4+b+c+e+f\right)^16^24^a+b+c+d+e+f-63^6\) |
For example, suppose we have the degree sequence \(S=8^{2}6^{1}5^{2}4^{1}3^{4}\). We see \(n=10\) and \(\sum d_{i}=48=2\left(3n-6\right)\), so we have the right degree sum for a 3-tree [5]. The \(3^{4}\) and \(5^{2}\) shows it must fall under Case 3, subcase ABDF. Then \(a+b+d+f=5\), so \(a=2\) and \(b=d=f=1\). Thus \(S\) is the degree sequence of a 3-tree with diameter 2.
Thanks to Zhongyuan Che for discussing this problem with me, and particularly for helping to develop Proposition 2.3, Lemma 2.5, and the argument in the proof of Theorem 4.2.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.