Graph Smoothing

 

 

Graph smoothing, also known as smoothing away or smoothing out, is the process of replacing edges  and  incident at a vertex  of vertex degree 2 by a single new edge  and removing the vertex  (Gross and Yellen 2006, p. 293).

A tree which is smoothed until no vertices of degree two remain is known as a series-reduced tree.

The process of smoothing simpe cyclic graphs is less well defined, since while a single smoothing of the cycle graph  gives the graph  for , if additional smoothing is performed, the graph  is smoothed to the dipole graph  which is no longer a simple graph but rather a multigraph since it contains two edges between its two vertices. Similarly, smoothing  give the bouquet graph  which is no longer a simple graph but rather a pseudograph since it consists of a single vertex connected to itself by a graph loop. Finally, according to Gross and Yellen (2006, p. 293), it is not permitted to smooth away the sole remaining vertex of .

Graph smoothing is the opposite of graph subdivision.

---

REFERENCES

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, p. 293, 2006.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength