chapter  Chapter 16
8 Pages

f-Graph: Bounded Vertex Degree

WithLouis V. Quintas, Edgar G. DuCasse

A graph with no vertex of degree greater than a constant f is said to be of bounded vertex degree f and in an appropriate context is referred to simply as an f-graph. In electrical, communication, and transportation models the number of edges incident to a vertex is naturally bounded by physical or monetary constraints. The bound on the number of vertices in such models, although present, is not as restricted as the bound on the vertex degrees. Although the preceding was not applicable to many applications, this clearly suggested that a focused study of the evolution and structure of graphs with a bounded degree was needed. Many papers with f-graphs in this context have appeared. Today f-graphs are studied from many different points of view both theoretically and in applications. Namely, their properties and structure are being studied, such as their graph invariants, their algebraic properties and their probabilistic/statistical characteristics.