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, v0, v1, ..., vn, so that the edges are vi−1vi 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 v1, ..., vn so that the edges are vi−1vi for each i = 2,...,n in addition to vnv1. 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.

Read more about this topic:  Graph (mathematics)

Famous quotes containing the word important:

    “But a dog teaches a boy fidelity, perseverance, and to turn around three times before lying down—very important traits in times like these. In fact, just as soon as a dog comes along who, in addition to these qualities, also knows when to buy and sell stocks, he can be moved right up to the boy’s bedroom and the boy can sleep in the dog house.”
    —Robert Benchley (1889–1945)