Interesting Graph Theory Terms

The following is a few of the more unique graph theory terms which I have misused in the past.

  • A giant component is a connected subgraph that contains a majority of the entire graph’s nodes
  • The order of the graph is the number of vertices, and the size is the number of edges.
  • A walk is an alternating sequence of vertices and edges, beginning and ending with a vertex. A closed walk starts and ends son the same vertex. An open walk doesn’t. A trail is a walk where all the edges are distinct.
  • An (open) neighborhood of a vertex v is all the vertices adjacent to v, but excluding v. A closed neighborhood includes v.
  • This one is trivial but I’ve seen it misused often which is can be a big source of confusion. For an edge (i,j), i is the tail and j is the head. I remember that by thinking of the head as the arrowhead.
  • The zweieck of an undirected edge e=(u,v) is the pair of directed edges (u,v) and (v,u). It’s a german word that means “biangle”.
  • An orientation is an assignment of directions to the edges of an undirected graph. A strong orientation is an orientation that produces a strongly connected digraph.

Leave a Reply

Your email address will not be published. Required fields are marked *