Root graph

In graph theory, a root graph is a graph in which one vertex is labeled in order to distinguish it from other vertices. This special vertex is called the root of the graph ^[1] ^[2] .

The number of root graphs for 1, 2, ... vertices is 1, 2, 6, 20, 90, 544, ... (sequence A000666 in OEIS ).

Root graphs can be combined using the root product of graphs .

Content

Root Trees

The root tree is a tree in which one vertex is selected (the root of the tree). Formally, the root tree is defined as a finite set $T$ ${\ displaystyle T}$ one or more nodes with the following properties:

there is one root of a tree $T$ ${\ displaystyle T}$ ;
the remaining nodes (with the exception of the root) are distributed among $m\geq 0$ ${\ displaystyle m \ geq 0}$ disjoint sets $T_{1},...,T_{m}$ ${\ displaystyle T_ {1}, ..., T_ {m}}$ , and each of the sets is a root tree; trees $T_{1},...,T_{m}$ ${\ displaystyle T_ {1}, ..., T_ {m}}$ are called subtrees of this root $T$ ${\ displaystyle T}$ .

Related definitions

Node level - path length from root to node. You can define recursively:

tree root level $T$ ${\ displaystyle T}$ equals 0;
the level of any other node is one greater than the root level of the nearest subtree of the tree $T$ ${\ displaystyle T}$ containing this node.

A tree with a marked top is called a root tree .
- $m$ ${\ displaystyle m}$ tier wood $T$ ${\ displaystyle T}$ - many tree nodes, at the level $m$ ${\ displaystyle m}$ from the root of the tree.
- partial order on vertices: $u\prec v$ ${\ displaystyle u \ prec v}$ if vertices $u$ ${\ displaystyle u}$ and $v$ ${\ displaystyle v}$ different and top $u$ ${\ displaystyle u}$ lies on the (unique!) elementary chain connecting the root to the vertex $v$ ${\ displaystyle v}$ .
- root subtree with root $v$ ${\ displaystyle v}$ - subgraph $\{v\}\cup \{w\mid v<w\}$ ${\ displaystyle \ {v \} \ cup \ {w \ mid v <w \}}$ .
- In a context where a tree is supposed to have a root, a tree without a selected root is called free .

Notes

↑ Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .
↑ Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society . - 1955. - Vol. 78 - p . 445-463 . - DOI : 10.1090 / S0002-9947-1955-0068198-2 .

Literature

CD Godsil, BD McKay. A new graph product and its spectrum // Bull. Austral. Math Soc. - 1978. - V. 18 , no. 1 . - pp . 21-28 . - DOI : 10.1017 / S0004972700007760 .
Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society . - 1955. - Vol. 78 - p . 445-463 . - DOI : 10.1090 / S0002-9947-1955-0068198-2 .

External links

Weisstein, Eric W. Rooted Graph (English) on Wolfram MathWorld .

[Zwillinger2011-1] Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae, 32nd Edition. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .

[Harary55-2] Frank Harary. The number of linear, directed, rooted, and connected graphs // Transactions of the American Mathematical Society . - 1955. - Vol. 78 - p . 445-463 . - DOI : 10.1090 / S0002-9947-1955-0068198-2 .