\(k\)-paths of \(k\)-trees (Q2089555)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(k\)-paths of \(k\)-trees |
scientific article |
Statements
\(k\)-paths of \(k\)-trees (English)
0 references
22 October 2022
0 references
Let \(k\) be a non-negative integer. A family of graphs that can be obtained in \(k\) steps from a complete graph \(K_{t+1}\), where we add a new vertex \(v_i\), \(i\in\{1,\dots,k\}\), at each step and connect \(v_i\) with an edge to every vertex of some already existing clique \(K_t\), are called \(t\)-trees. Clearly, trees are 1-trees. A \(t\)-leaf is a vertex of a \(t\)-tree of degree \(t\). A \(t\)-path is a sequence of \(t+1\)-cliques such that any two consecutive \(t+1\)-cliques have a \(t\)-clique in their intersection. The first result of this work is a forbidden subgraphs characterization of \(t\)-paths among \(t\)-trees and the second result describes the diameter of a \(t\)-tree with respect to \(t\)-paths existing in the mentioned \(t\)-tree. For the entire collection see [Zbl 1495.05003].
0 references
\(k\)-tree
0 references
\(k\)-path
0 references
diameter
0 references