Rooted product of graphs

Rooted product of graphs

In mathematical graph theory, the rooted product of a graph "G" and a rooted graph "H" is defined as follows: take |"V"("G")| copies of "H", and for every vertex v_i of "G", identify v_i with the root node of the "i"-th copy of "H".

More formally, assuming that "V"("G") = {"g"1, ..., "g""n"}, "V"("H") = {"h"1, ..., "h""m"} and that the root node of "H" is h_1, define

:G circ H := (V, E)

where

:V = left{(g_i, h_j): 1leq ileq n, 1leq jleq m ight}

and

:E = left{((g_i, h_1), (g_k, h_1)): (g_i, g_k) in E(G) ight} cup igcup_{i=1}^n left{((g_i, h_j), (g_i, h_k)): (h_j, h_k) in E(H) ight}

If "G" is also rooted at "g"1, one can view the product itself as rooted, at ("g"1, "h"1). The rooted product is a subgraph of the cartesian product of the same two graphs.

The rooted product is especially relevant for trees, as the rooted product of two trees is another tree. For instance, Koh et al. (1980) used rooted products to find graceful numberings for a wide family of trees.

References

*cite journal
author = Godsil, C. D.; McKay, B. D.
title = A new graph product and its spectrum
journal = Bull. Austral. Math. Soc.
volume = 18
year = 1978
issue = 1
pages = 21–28
id = MathSciNet | id = 0494910
url = http://cs.anu.edu.au/~bdm/papers/RootedProduct.pdf

*cite journal
author = Koh, K. M.; Rogers, D. G.; Tan, T.
title = Products of graceful trees
journal = Discrete Mathematics
volume = 31
year = 1980
issue = 3
pages = 279–292
id = MathSciNet | id = 0584121
doi = 10.1016/0012-365X(80)90139-9


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Graph product — A graph product is a binary operation on graphs. There are several similarly defined operations on graphs, called product . Given two graphs G1 and G2 , their product H is a graph such that * the vertex set of H is the Cartesian product V(G 1)… …   Wikipedia

  • Direct product — In mathematics, one can often define a direct product of objects already known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one… …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Combinatorial species — In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for analysing discrete structures in terms of generating functions. Examples of discrete structures are (finite) graphs, permutations, trees, and… …   Wikipedia

  • Bass–Serre theory — is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Charles Sanders Peirce —  B …   Wikipedia

  • Butcher group — In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher by Hairer Wanner (1974), is an infinite dimensional group first introduced in numerical analysis to study solutions of non linear ordinary differential… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”