Separating subgraphs in k-trees: Cables and caterpillars (Q795842): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Properties and characterizations of <i>k</i> ‐trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Incidence matrices and interval graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Trees with Hamiltonian square / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursive Graphs, Recursive Labelings and Shortest Paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3901535 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On simple characterizations of k-trees / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:20, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Separating subgraphs in k-trees: Cables and caterpillars |
scientific article |
Statements
Separating subgraphs in k-trees: Cables and caterpillars (English)
0 references
1984
0 references
The class of k-trees has been defined recursively by starting with a \(k+1\)-clique and successively adding one new vertex joined to an existing k-clique. Ordinary trees are 1-trees. The author extends various concepts such as paths and caterpillars from ordinary trees to k-trees. He finds that the union of all cliques that separate u from v comprise a k-1- caterpillar with additional restrictions. Since k-trees are k-connected, he calls the union of k vertex disjoint paths from u to v a u,v-cable. The cable distance is the ''length'' of a shortest cable. The shortest cable is found to be unique and induced by the caterpillar mentioned above. A sufficient condition is given to demonstrate that cable distance may exceed ordinary distance.
0 references
k-tree
0 references
cliques
0 references
caterpillar
0 references
cable distance
0 references