graphs · math

Combinatorics and Graph Theory

April 30, 2024 (last updated May 9, 2024)

1.1.2 The Basics

Vertex set of a graph G is denoted $V(G)$
edge set denoted $E(G)$ or $E$
we may refer to them simply as V(E)
edges are denoted ${u,v}$ or simply as $uv$
directed graph:
- $E$ is a set of ordered pairs of vertices
multigraph:
- $E$ is a multiset and may contain repeated elements
pseudograph:
- allowing edges to connect a vertex to itself (loops)
infinite graphs:
- when $V$ or $E$ can be an infinite set
the order of a graph:
- the cardinality (size, number of elements) of its vertex set
the size of a graph:
- the cardinality of its edge set
adjacent vertices:
- if $uv \in E$ , then u and v are adjacent
- in other words, vertices are adjacent if they are connected by an edge.
nonadjacent vertices:
- are not connected by an edge.
incidence:
- $v$ is incident of $e$ if $v$ is an end vertex for $e$ .
(open) neighbourhood of a vertex $v$ :
- $N(v)$ : the set of vertices adjacent to $v$
closed neighbourhood of a vertex $v$ :
- $N[v]$ is the set ${v} \cup N(v)$
neighbourhood of a set of vertices
- $N(S)$ : the union of neighbourhood of vertices in $S$
- similar definition for closed neighbourood
the degree of $v$ :
- $deg(v)$ : the number of edges incident with v
- aka number of outgoing edges of v
- in simple graphs, this is the same as the cardinality of the neighbourhood of $v$
maximum degree of a graph $G$
- denoted $\Delta(G)$ is the $max \{deg(v) | v \in V(G)\}$
minimum degree: similar definition as max

walk
- a sequence of of vertices $v_1,...,v_k$ such that ${v_i}v_{i+1} \in E$
- aka each subsequent vertex paired make an edge
path
- where the vertices in a walk are distinct
trail
- where the edges in a walk are distinct
every path is a trail, but not every trail is a path

theorem: in a graph G with vertices u and v, every u-v walk contains a u-v path,

vertex deletion:
- we let $G-v$ denote the graph obtained by removing $v$ and all edges incident with $v$
- - if $S$ is a set of vertices, we let $G-S$ denote the graph obtained by removing each vertex of S and all the incident edges.
edge deletion:
- …
connected component:
- each maximal connected piece of a graph is called a connected component.
cut vertex
- if the deletion of a vertex $v$ from $G$ causes the number of compnents to increase, then $v$ is called a cut vertex
cut set
- a proper subset S of vertices of a graph G is called a vertex cut set if the graph G - S is disconnected
complete graph
- A graph where each vertex is adjacent to every other vertex (has an edge between them)
- complete graphs do not have any cut sets.
connectivity
- the connectivity of $G$ denoted $\kappa(G)$ is the minimum size of a cut set $G$ .
- a graph is k-connected if $k \leq \kappa(G)$

undefinedundefined

Special types of graphs

isomorphic

Graphs $G$ and $H$ are said to be isomorphic if there exists a one-to-one mapping $f : V(G) → V(H)$ that preserves adjacency
the mapping is called an isomorphism
when two graphs are isomorphic you can say G = H or G is H
determining if two graphs are isomorphic is generally a difficult problem to solve

Combinatorics and Graph Theory, p.30
the distance from vertex u to vertex v
- is the length (number of edges) of a shortest $u-v$ path in G
- we denote this distance by $d(u,v)$
the eccentricity of vertex v, denoted $ecc(v)$ $ecc (v)$
- the greatest distance from v to any other vertex
in a connected graph G the radius of G denoted $rad(G)$ $r a d (G)$
- is the value of the smallest eccentricity
the diameter of G, diam(G)
- the value of the greatest eccentricity
the center of the graph G
- the set of vertices, v, s/t ecc(v) = rad(G)
the periphery of G
- the set of vertices u, s/t ecc(u) = diam(G)