Graph (mathematics) - Important Graphs

Important Graphs

Basic examples are:

• In a complete graph, each pair of vertices is joined by an edge; that is, the graph contains all possible edges.
• In a bipartite graph, the vertex set can be partitioned into two sets, W and X, so that no two vertices in W are adjacent and no two vertices in X are adjacent. Alternatively, it is a graph with a chromatic number of 2.
• In a complete bipartite graph, the vertex set is the union of two disjoint sets, W and X, so that every vertex in W is adjacent to every vertex in X but there are no edges within W or X.
• In a linear graph or path graph of length n, the vertices can be listed in order, v₀, v₁, ..., v_n, so that the edges are v_i−1v_i for each i = 1, 2, ..., n. If a linear graph occurs as a subgraph of another graph, it is a path in that graph.
• In a cycle graph of length n ≥ 3, vertices can be named v₁, ..., v_n so that the edges are v_i−1v_i for each i = 2,...,n in addition to v_nv₁. Cycle graphs can be characterized as connected 2-regular graphs. If a cycle graph occurs as a subgraph of another graph, it is a cycle or circuit in that graph.
• A planar graph is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect (i.e., embedded in a plane).
• A tree is a connected graph with no cycles.
• A forest is a graph with no cycles (i.e. the disjoint union of one or more trees).

More advanced kinds of graphs are:

• The Petersen graph and its generalizations
• Perfect graphs
• Cographs
• Chordal graphs
• Other graphs with large automorphism groups: vertex-transitive, arc-transitive, and distance-transitive graphs.
• Strongly regular graphs and their generalization distance-regular graphs.