Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-06T07:48:40.163Z Has data issue: false hasContentIssue false
  • English
  • Français

Properties and characterizations of k-trees

Part of: Graph theory

Published online by Cambridge University Press:  26 February 2010

L. W. Beineke  and
R. E. Pippert
L. W. Beineke
Affiliation:
Purdue University, Fort Wayne, Indiana, U.S.A.
R. E. Pippert
Affiliation:
Purdue University, Fort Wayne, Indiana, U.S.A.
Get access

Extract

Trees are basic in graph theory and its applications to many fields, such as chemistry, electric network theory, and the theory of games. König [7; 47-48] gives an interesting historical account of independent discoveries of trees by Kirchhoff, Cayley, Sylvester, Jordan, and others who were working in a variety of fields.

There are many equivalent ways of defining trees, the most common being: A tree is a graph which is connected and has no circuits. Figure 1 shows the trees with up to six vertices; those with up to 10 vertices can be found in Harary [5; 233–234]. Some other possible definitions of a tree are the following: (1) A tree is a graph which is connected and has one more vertex than edge. (2) A tree is a graph which has no circuits and has one more vertex than edge. For these and other characterizations see Berge [4; 152ff.] and Harary [5; 32ff.]. A less common definition is by induction: The graph consisting of a single vertex is a tree, and a tree with n + 1 vertices is obtained from a tree with n vertices by adding a new vertex adjacent to exactly one other vertex.

MSC classification

Secondary: 05C05: Trees
Type
Research Article
Information
Mathematika , Volume 18 , Issue 1 , June 1971 , pp. 141 - 151
Copyright
Copyright © University College London 1971

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Beineke, L. W. and Moon, J. W., “Several proofs of the number of labelled 2-dimensional trees”. Chapter in Proof Techniques in Graph Theory, Harary, F., ed. (Academic Press, New York, 1969, pp. 11–20).Google Scholar
2.Beineke, L. W. and Pippert, R. E., The number of labelled k-dimensional trees,” J. Combinatorial Theory, 6 (1969), 200–205.CrossRefGoogle Scholar
3.Beineke, L. W. and Pippert, R. E., “The number of labelled dissections of a k-ball,” Math. Ann. (to appear).Google Scholar
4.Berge, C., The Theory of Graphs and its Applications (Methuen, London, 1962).Google Scholar
5.Harary, F., Graph Theory (Addison-Wesley, Reading, Mass., 1969).CrossRefGoogle Scholar
6.Harary, F. and Palmer, E. M., “On acyclic simplicial complexes,” Mathematika, 15 (1968), 115–122.CrossRefGoogle Scholar
7.Konig, D., Theorie der Endlichen und Unendlichen Graphen (Leipzig, 1936; Reprinted Chelsea, New York, 1950).Google Scholar
8.Moon, J. W., “The number of labelled k-trees,” J. Combinatorial Theory, 6 (1969), 196–199.CrossRefGoogle Scholar
9.Palmer, E. M., “On the number of labelled 2-trees,” J. Combinatorial Theory, 6 (1969), 206–207.CrossRefGoogle Scholar
10.Pippert, R. E. and Beineke, L. W., “Characterizations of 2-dimensional trees”. Chapter in The Many Facets of Graph Theory, Chartrand, G. and Kapoor, S. F., eds. (Springer-Veilag, Berlin, 1969, pp. 250–257).Google Scholar