Graph Theory Definitions for Midterm 1

  1. Neighbourhood
    The neighbourhood of a vertex v is the set of neighbours of v, and is denoted by NG(v)
  2. Underlying simple graph of G
    The simple graph obtained by deleting all loops and all but one of each set of multiple edges
  3. Graph Complement
    • simple graph with vertex set V(chart?chf=bg,s,00000000&cht=tx&chl=%5Cbar%20G&chs=32x40)=V(G) in which uv∈ E(chart?chf=bg,s,00000000&cht=tx&chl=%5Cbar%20G&chs=32x40) if and only if uv ∉ E(G).
    • The edge set of chart?chf=bg,s,00000000&cht=tx&chl=%5Cbar%20G&chs=32x40 is the set of nonedges of G.
    • chart?chf=bg,s,00000000&cht=tx&chl=%5Cbar%20%7B%5Cbar%20G&chs=36x50=G.
  4. Clique
    a set of pairwise adjacent vertices.
  5. clique number and symbol
    • cardinality of a largest clique in G
    • ω(G)
  6. independent/stable set
    set of pariwise nonadjacent vertices
  7. independence number and symbol
    • cardinality of a largest independent set in G
    • α(G)
  8. chromatic number and symbol
    • the minimum number of colours needed to colour the vertices of G so that distinct adjacent vertices receive different colours
    • χ(G)
  9. k-partite graph
    the vertex set of a k-partite graph can be partitioned into k independent sets
  10. planar
    A graph is planar if it is possible to draw a diagram of it in the plane without crossing.
  11. path
    a simple graph whose vertices are ordered so that two vertices are adjacent if and only if they're consecutive
  12. cycle
    a graph whose vertices are ordered in a circle so that two vertices are adjacent if and only if they are consecutive on the circle.
  13. subgraph
    a subgraph of G is a graph H such that V(H)⊆V(G) and E(H)⊆E(G), and the assignment of endpoints to edges in H is the same as in G
  14. degree of a vertex v in a graph G
    the number of edges incident with v, with each loop counting as two edges.
  15. minimum degree symbol
  16. maximum degree symbol
  17. incidence matrix and symbol
    • M(G)
    • nxm matrix with rows as the vertex set and columns the edge set, in which the ij0th entri is the number of times vi is incident with ej
  18. adjacency matrix of G and symbol
    • A(G)
    • nxn matrix with rows and columns indexed by the vertex set of G, in which the ij-th entry is the number of edges joining vi and vj in G
  19. Two graphs G and H are identical (equal) if
    V(G)=V(H), E(G)=E(H)
  20. Isomorphism
    A simple graph G is said to be isomorphic to a simple graph H if there is a bijection f:V(G)→V(H) such that uv∈E(G)⇔ f(u)f(v)∈E(H)
  21. Line graph
    the simple graph with vertex set V(L(G))=E(G) in which two vertices are joined if and only if they are adjacent edges in G.
  22. self complementary graphs
    A simple graph G is self complementary if G≃chart?chf=bg,s,00000000&cht=tx&chl=%5Cbar%20G&chs=32x40
  23. a decomposition of a graph G
    • a list of subgraphs of G such that each edge of G lies in exactly one subgraph in the list.
    • The edge sets of the subgraphs in the list partition the edges set of G.
  24. k-regular
    a graph is k-regular if dG(V) = k for all v∈V(G)
  25. girth
    • length of a shortest cycle measured in number of edges
    • If G has no cycles we say G has infinite girth
  26. Union of Graphs G1, G2, ..., Gk
    the graph with vertex setchart?chf=bg,s,00000000&cht=tx&chl=%5Ccup%20_%7Bi%3D1%7D%20%5Ek%20V(G_i)&chs=164x80 and the edge set chart?chf=bg,s,00000000&cht=tx&chl=%5Ccup%20_%7Bi%3D1%7D%20%5Ek%20E(G_i)&chs=164x80
  27. Disjoint union or sum
    If the graphs G1,G2,Gk have pairwise-disjoint vertex sets, then the disjoint union or sum is denoted by G1+G2+...+Gk
  28. H-Free
    A graph G is H-free if G has no induced subgraph isomorphic to H.
  29. walk of length k
    an ordered list of alternating vertices and edges
  30. trail
    a walk with no repeated edge
  31. path
    a walk with no repeated vertex (and no repeated edge)
  32. length of a walk, trail, path or cycle
    number of edges, including repetitions if any
  33. concatenation in a graph G
    • Given a (u,v)-path P and a (v,w)-path Q in G, the concatenation PQ is the (uw,)-walk obtained by following P from u to v, then following Q from v to w.
    • P-1 denotes the (v,u)-path obtained by traversing P backwards from v to u.
  34. cut-edge (cut-vertex)
    a edge e (vertex v) such that G-e (G-v) ihas more components than G
  35. Eulerian trail
    a trail which uses every edge of G exactly once
  36. When is a graph Eulerian?
    • If it contains a Eulerian circuit, which is a closed Eulerian trail
    • Result: A graph G is Eulerian if and only if it has at most one nontrivial component and is even.
  37. even (odd) graph
    a graph in which all vertices have even (odd) degree.
  38. maximal path in a graph G
    a path which is not contained in a longer path of G
  39. maximum path in G
    a path of maximum length.
  40. order and symbol
    • n(G)
    • Order is the cardinality of the vertex set of G
  41. size and symbol
    • e(G)
    • Size is the cardinality of the edge set of G
  42. degree sequence
    is the list of vertex degrees of a graph, usually written in nonincreasing order.
  43. graphic
    a degree sequence of nonnegative integers is graphic if there is a simple graph with degree sequence d.
  44. acyclic
    graph with no cycles
  45. forest
    acyclic graph
  46. tree
    connected acyclic graph
  47. leaf or pendant vertex
    vertex with degree 1
  48. spanning tree of graph G
    • spanning subgraph H of G that is a tree
    • ie, V(G)=V(G)
  49. distance from u to v
    • if vertices u and v are connected in graph G, then the distance from u to v denoted by dG(u,v) is the length of a shortest (u,v)-path in G.
    • If u and v are not connected in G, then dG(u,v) = ∞
  50. diameter and symbol
    • diam(G)
    • maximum distance between any two vertices of G
    • Not the length of the longest path but the length of the longest shortest path
  51. eccentricity of a vertex u in a graph G and symbol
  52. radius of a graph G and symbol
    • rad(G)
    • chart?chf=bg,s,00000000&cht=tx&chl=rad(G)%3Dmin_%7Bu%5Cep%20V(G)%7D%5Cep(u)&chs=372x50
  53. center of a graph G
    • Subgraph of G induced by the vertices of minimum eccentricity
    • ie, the vertices of u such that chart?chf=bg,s,00000000&cht=tx&chl=%5Cep%20(u)%3Drad(G)&chs=206x38
  54. contracted and symbol
    • An edge e of a graph G is said to be contracted if it is deleted and its endpoints are identified.
    • G•e
  55. optimal tree
    minimum-weight spanning tree
  56. greedy algorithms
    locally optimal heuristics (practical method)
Card Set
Graph Theory Definitions for Midterm 1
Graph Theory Definitions for Midterm 1