Graph Theory Definitions for Midterm 1

The neighbourhood of a vertex v is the set of neighbours of v, and is denoted by N_G(v)

The simple graph obtained by deleting all loops and all but one of each set of multiple edges

• simple graph with vertex set V()=V(G) in which uv∈ E() if and only if uv ∉ E(G).
• The edge set of is the set of nonedges of G.
• =G.

a set of pairwise adjacent vertices.

• cardinality of a largest clique in G
• ω(G)

set of pariwise nonadjacent vertices

• cardinality of a largest independent set in G
• α(G)

• the minimum number of colours needed to colour the vertices of G so that distinct adjacent vertices receive different colours
• χ(G)

the vertex set of a k-partite graph can be partitioned into k independent sets

A graph is planar if it is possible to draw a diagram of it in the plane without crossing.

a simple graph whose vertices are ordered so that two vertices are adjacent if and only if they're consecutive

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.

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

the number of edges incident with v, with each loop counting as two edges.

δ(G)

Δ(G)

• 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 v_i is incident with e_j

• 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 v_i and v_j in G

V(G)=V(H), E(G)=E(H)

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)

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.

A simple graph G is self complementary if 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.

a graph is k-regular if d_G(V) = k for all v∈V(G)

• length of a shortest cycle measured in number of edges
• If G has no cycles we say G has infinite girth

the graph with vertex set and the edge set

If the graphs G_1,G_2,G_k have pairwise-disjoint vertex sets, then the disjoint union or sum is denoted by G₁+G₂+...+G_k

A graph G is H-free if G has no induced subgraph isomorphic to H.

an ordered list of alternating vertices and edges

a walk with no repeated edge

a walk with no repeated vertex (and no repeated edge)

number of edges, including repetitions if any

• 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.

a edge e (vertex v) such that G-e (G-v) ihas more components than G

a trail which uses every edge of G exactly once

• 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.

a graph in which all vertices have even (odd) degree.

a path which is not contained in a longer path of G

a path of maximum length.

• n(G)
• Order is the cardinality of the vertex set of G

• e(G)
• Size is the cardinality of the edge set of G

is the list of vertex degrees of a graph, usually written in nonincreasing order.

a degree sequence of nonnegative integers is graphic if there is a simple graph with degree sequence d.

graph with no cycles

acyclic graph

connected acyclic graph

vertex with degree 1

• spanning subgraph H of G that is a tree
• ie, V(G)=V(G)

• if vertices u and v are connected in graph G, then the distance from u to v denoted by d_G(u,v) is the length of a shortest (u,v)-path in G.
• If u and v are not connected in G, then d_G(u,v) = ∞

• 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

• rad(G)
• 

• Subgraph of G induced by the vertices of minimum eccentricity
• ie, the vertices of u such that

• An edge e of a graph G is said to be contracted if it is deleted and its endpoints are identified.
• G•e

minimum-weight spanning tree

locally optimal heuristics (practical method)