Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 01 introduction
Tags: fromMath mathToDef hasSeenConjDef toBinaryFunction toBinaryRelation dd defToAlgebra examplesSwitchExample1 graph mathToSee setMultiplication typToBinary

Name: A graph
Definition: A pair \((V(G), E(G))\) of disjoint sets
Page: 2
Chapter: 1
Definition2: An incidence function \(\psi_G\) which associates to each edge a set of one or two elements of \(V\)
Conjdef: Both
Representation: small circles, and some line joining them

Name: The set of edges of \(G\)
Definition: \(E(G)\)
Page: 2
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph

Name: The set of vertices of \(G\)
Definition: \(V(G)\)
Page: 2
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph

Name: An edge which joins \(u\) and \(v\)
Definition: An element \(e\in E(G)\) such that \(\psi_G(e)=\{u,v\}\)
Page: 2
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph,
\(u,v\in V(G)\)

Name: The ends of \(e\)
Definition: The elements of \(\psi_G(e)\)
Page: 2
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph,
\(e\in E(G)\)

Name: The order of \(G\)
Definition: The cardinality of \(V(G)\)
Page: 2
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph
Notation: \(v(G)\)

Name: The size of \(G\)
Definition: The cardinality of \(E(G)\)
Page: 2
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph
Notation: \(e(G)\)

Name: An element incident to \(e\)
Definition: A vertex \(v\in V(G)\) such that \(v\in \psi_G(e)\)
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph,
\(e\in E(G)\)

Name: An element incident to \(v\)
Definition: An edge \(e\in V(G)\) such that \(v\in \psi_G(e)\)
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph,
\(v\in V(G)\)

Name: An element adjacent to \(v\)
Definition: A vertex \(v'\in V(G)\) such that \(\psi_G(e)=\{v,v'\}\) for some \(e\in E(G)\)
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph,
\(v\in V(G)\)

Name: Two neighbors
Definition: Two adjacent vertices.
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph

Name: The set of neighbors of \(v\)
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph,
\(v\in V(G)\)
Notation: \(N_G(v)\)

Name: A loop
Definition: An edge \(e\in E(G)\) such that \(\psi(e)\) is a singleton.
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph

Name: A link
Definition: An edge \(e\in E(G)\) such that \(\psi(e)\) contains two elements.
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph

Name: Parallel edges
Definition: Two edges \(e,f\) such that \(\psi(e)=\psi(f)\).
Page: 3
Chapter: 1
Variables: \(G=(V(G), E(G))\) a graph

Name: A finite/countable graph
Definition: A graph whose vertex set and edge set are finite/countable.
Page: 3, 36
Chapter: 1, 1
Section: 1, 6

Name: The null graph
Definition: The graph \((\emptyset,\emptyset)\).
Page: 3
Chapter: 1

Name: A trivial graph
Definition: A graph with a unique vertex.
Page: 3
Chapter: 1

Name: A nontrivial graph
Definition: A graph wich is not trivial.
Page: 3
Chapter: 1

Name: A simple graph
Definition: A graph without loops nor parallel edges.
Page: 3
Chapter: 1

Name: An edge of \(G\)
Definition: An element of \(E\)
Page: 4
Chapter: 1
Variables: \(G=(V,E)\) a simple graph,
Typ: An unordered pair of element

Name: The complete graph of size \(m\)
Definition: A simple graph of size \(m\) in which any two vertices are adjacent.
Page: 4, 14
Chapter: 1
Variables: \(m\in\mathbb N\)
Notation: \(K_m\)

Name: An empty graph
Definition: A graph without edges.
Page: 4
Chapter: 1

Name: A bipartition of \(G\)
Definition: A partition \((X,Y)\) of \(E\) such that for each \((u,v)\in E\), \(u\in X\iff v\in Y\).
Page: 4
Chapter: 1
Variables: \(G=(V,E)\)

Name: A bipartite graph
Definition: A graph which admits a bipartition.
Page: 4
Chapter: 1

Name: Its parts
Definition: \(X\) and \(Y\).
Page: 4
Chapter: 1
Variables: \(G=(V,E)\) a bipartite graph,
\((X,Y)\) its bipartition

Name: A complete bipartite graph
Definition: A graph \(G=(\{v_1,\dots,v_m,v'_1,\dots,v'_n\}, \{\{v_i,v'_j\}\mid 1\le i\le m, 1\le j\le n\})\).
Page: 4, 14
Chapter: 1
Variables: \(m,n\in\mathbb N\)
Context: Graph
Notation: \(K_{m,n}\)

Name: A star
Definition: A complete bipartite graph with a part of cardinality 1.
\((\{v_0\}\cup V, \{v_0\}\times V)\) for some set of vertices \(V\)
Page: 4
Chapter: 1
Context: Graph

Name: The \(n\)-path
Definition: The graph \((\{v_1,\dots,v_n\},\{\{v_{i},v_{i+1}\}\mid 1\le i<n\})\).
Page: 4, 14
Chapter: 1
Section: 1, 2
Variables: \(n\in\mathbb N\)
Context: Graph
Notation: \(P_n\)

Name: A \(n\)-cycle
Definition: A graph of the form \((\{v_1,\dots,v_n\},\{\{v_{i},v_{i+1}\}\mid 1\le i<n\}\cup\{\{v_n,v_1\}\})\).
Page: 4, 14
Chapter: 1
Section: 1,2
Variables: \(n\in\mathbb N\)
Notation: \(C_n\)

Name: The length of \(P\)
Definition: The number of edges of \(P\).
Page: 4
Chapter: 1
Variables: \(P\) a path

Name: The length of \(C\)
Definition: The number of edges of \(C\).
Page: 4
Chapter: 1
Variables: \(C\) a cycle
Context: Cycle

Name: A triangle
Definition: A 3-cycle.
Page: 4
Chapter: 1

Name: A quadrilateral
Definition: A 4-cycle.
Page: 4
Chapter: 1

Name: A pentagon
Definition: A 5-cycle.
Page: 4
Chapter: 1

Name: An hexagon
Definition: A 6-cycle.
Page: 4
Chapter: 1

Name: A connected (di)graph
Definition: A graph \(G=(V,E)\) such that, for each partition \((X,Y)\) of \(V\), there is an edge from \(X\) to \(Y\).
Page: 5, 79
Chapter: 1, 3
Section: 1, 1
Extra: other defs

Name: A planar graph
Definition: A graph \(G=(V,E)\) which can be represented in the plane without intersecting edges.
Page: 5
Chapter: 1

Name: A planar embedding of \(G\)
Definition: A representation of \(G\) in the plane, without edges intersecting.
Page: 5
Chapter: 1
Variables: \(G\) a planar graph

Name: An embedding of \(G\)
Definition: A representation of \(G\), on some surface, without edges intersecting.
Page: 6
Chapter: 1
Variables: \(G\) a graph

Name: The incidence matrix of \(G\)
Definition: The \(V\times E\)-matrix whose \((v,e)\) entry is the number of times that vertex and edge are incident.
Page: 6
Chapter: 1
Variables: \(G=(V,E)\) a graph,

Name: The adjacency matrix of \(G\)
Definition: The \(V\times V\)-matrix whose \((u,v)\) entry is the number of edges joining \(u\) and \(v\) (arc with tail \(u\) and head \(v\)).
Page: 6, 36
Chapter: 1, 1
Section: 1, 5
Variables: \(G=(V,E)\) a (di)graph
Index: , 13
Kind: , exercice

Name: An adjacency list
Definition: A list of the form \(\left(N(v)\right)_{v\in V}\).
Page: 6
Chapter: 1
Variables: \(G=(V,E)\) a graph,

Name: A bipartite adjacency matrix of \(G\)
Definition: The restriction of the adjacency matrix to \(X\times Y\).
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a bipartite graph,
\(X,Y\) a partition of \(G\)

Name: The degree of \(v\)
Definition: The number of edges incident to \(v\) in \(G\), loop counting twice.
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a (di)graph,
\(v\in V\)
Notation: \(d(v)\)

Name: The minimum degree of \(G\)
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a (di)graph
Notation: \(\delta(G)\)

Name: The maximal degree of \(G\)
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a (di)graph
Notation: \(\Delta(G)\)

Name: The average degree of \(G\)
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a (di)graph
Notation: \(d(G)\)

Name: An isolated vertex
Definition: A vertex \(v\) such that \(d(v)=0\).
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a bipartite graph,

Smaller0: \(\sum_{v\in V}d(v) \)
Greater0: \(2|E|\)
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a bipartite graph,
Kind: Theo
Smaller to greater: =

Question: Its number of vertices of odd degree is
Answer: even.
Page: 7
Chapter: 1
Variables: \(G=(V,E)\) a (di)graph
Index: 2
Kind: Cor

Name: A \(k\)-regular graph
Definition: A graph such that \(\delta(g)=\Delta(g)=k\).
Page: 7
Chapter: 1
Variables: \(k\in\mathbb N\)
Example: The complete bipartite graph with \(k\)-vertices in each part.
Example2: The complete graph with \(k+1\) vertices.

Name: A regular graph
Definition: A \(k\)-regular graph for some \(k\).
Page: 7
Chapter: 1

Name: A cubic graph
Definition: A \(3\)-regular graph.
Page: 7
Chapter: 1

Name: Counting in two ways
Definition: Considering a suitable matrix and computing the sum of its entries in two different ways.
Page: 9
Chapter: 1

Name: A \(k\)-partite graph
Definition: A graph \(G=(V,E)\) such that there exists a partition \(P_1,\dots,P_k\) of \(V\) such that for each \(uv\in E\), \(u\in P_i\implies v\not\in P_i\).
Page: 10
Chapter: 1
Kind: Ex

Name: A complete \(k\)-partite graph
Definition: A graph of the form \(G=(P_1\cup\dots \cup P_k,\bigcup_{1\le i<j\le k}P_i\times P_j)\).
Page: 10
Chapter: 1
Index: 11
Kind: Exercice

Name: A Turan graph
Definition: A complete \(k\)-partite graph, with \(n\) vertices, whose parts' size are \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\).
Page: 10
Chapter: 1
Variables: \(k,n\in\mathbb N\)
Notation: \(T_{k,n}\)
Index: 11
Kind: Exercice

Name: The complement of \(G\)
Definition: \((V,(V\times V)\setminus E)\).
Page: 10
Chapter: 1
Variables: \(G=(V,E)\) a graph
Notation: \(\overline G\)
Index: 17
Kind: Exercice

Name: graphic sequence of integer
Definition: A sequence \(\mathbf d=(d_1,\dots,d_n)\) such that there is a simple graph with degree sequence \(\mathbf d\).
Page: 11
Chapter: 1
Index: 18
Kind: Exercice

Name: Its eigenvalue
Definition: The eigenvalues of its adjacency matrix.
Page: 11
Chapter: 1
Variables: \(G=(V,E)\) a graph
Context: Graph
Index: 21
Kind: Exercice

Name: Its characteristic polynomial
Definition: The characteristic polynomial of its adjacency matrix.
Page: 11
Chapter: 1
Variables: \(G=(V,E)\) a graph
Index: 21
Kind: Exercice

Name: A strongly regular graph with parameters \((v,k,\lambda,\mu)\)
Definition: A \(k\)-regular graph, \(v(G)=v\), for \(u,v\in V\), if they are adjacent, then they have \(\lambda\) common neighbours, otherwise they have \(\mu\) common neighbours.
Page: 12
Chapter: 1
Variables: \(v,k,\lambda,\mu\) nonnegative integers
Index: 25
Kind: Exercice

Name: An isomorphism between \(G\) and \(H\)
Definition: Two bijections \(\theta:V(G)\to V(H)\), \(\phi:E(G)\to E(H)\), such that \(\phi_G(e)=uv\) iff \(\psi_H(\phi(e))=\theta(u)\theta(v)\).
Page: 12, 34
Chapter: 1, 1
Section: 2, 5
Variables: \(G=(V(G),E(G)),H=(V(H),E(H))\) two (di)graphs
Index: , 3
Kind: , ex

Name: The cycle of length \(m\)
Page: 14
Chapter: 1
Section: 2
Variables: \(m\in\mathbb N\)
Notation: \(C_{m}\)

Q: [...].
A: An isomorphism from \(G\) to \(G\)
Page: 15
Chapter: 1
Section: 2
Variables: \(G\) a graph
Name: An automorphism of \(G\)

Name: Asymmetric graph
Definition: A graph with no two similar vertices.
Page: 15
Chapter: 1
Section: 2
Variables: \(G\) a graph

Definition: The cardinality of \(\text{Aut}(G)\).
Page: 16
Chapter: 1
Section: 2
Variables: \(G\) a graph
Notation: \(\text{aut}(G)\)

Name: A labelled simple graph
Definition: A simple graph \(G=(V,E)\) with a function associating to each \(v\in V\) a unique label.
Page: 16
Chapter: 1
Section: 2

Name: The set of labelled simple graph of size \(n\)
Page: 16
Chapter: 1
Section: 2
Variables: \(n\in\mathbb N\)
Notation: \(\mathcal G_n\)

Question: \(\mathcal G_n\)'s cardinality is
Answer: \(2^{ n\choose 2}\).
Page: 16
Chapter: 1
Section: 2
Variables: \(n\in\mathbb N\)

Name: Its orbits
Definition: Its equivalence classes of the equivalent relation on the vertex set.
Page: 18
Chapter: 1
Section: 2
Variables: \(G\) a graph
Index: 13
Kind: Exercice

Name: A self-complementary graph
Definition: A graph \(G\) such that \(\overline G\cong G\).
Page: 19
Chapter: 1
Section: 2
Index: 16
Kind: Exercice

Name: An edge-transitive graph
Definition: A graph such that, for each edges \(uv\) and \(xy\), there is an automorphism sending \(uv\) to \(xy\).
Page: 19
Chapter: 1
Section: 2
Index: 17
Kind: Exercice

Name: Generalized Petersen Graph
Definition: \(\left(\{x_i,y_i\mid 1\le i\le n\},\{(x_i,x_{i+1}), (y_i,y_{i+k}), (x_i,y_i)\mid 0\le i< n\}\right) \)
Page: 20
Chapter: 1
Section: 2
Variables: \(n>2k\) integers
Notation: \(P_{k,n}\)

Name: A polyhedral graph
Definition: The 1-skeleton of a polyhedron.
Page: 21
Chapter: 1
Section: 3

Name: The \(1\)-skeleton of \(S\)
Definition: The graph whose vertices and edges are the ones of the solid \(S\).
Page: 21
Chapter: 1
Section: 3
Variables: \(S\) a solid

Name: A set system
Definition: An ordered pair \((V,\mathcal F)\), where \(V\) is a set of elements and \(\mathcal F\subseteq\mathcal P(V)\).
Page: 21
Chapter: 1
Section: 3
Name2: An hypergraph

Smaller0: \(\mathcal F\) is a set of pairs
Greater0: the set system is a loopless graph
Page: 21
Chapter: 1
Section: 3
Variables: \((V,\mathcal F)\) a set system
Hide middle: yes

Name: Its vertices
Definition: The elements of \(V\).
Page: 21
Chapter: 1
Section: 3
Variables: \((V,\mathcal F)\) a set system

Name: Its edges
Definition: The elements of \(\mathcal F\).
Page: 21
Chapter: 1
Section: 3
Variables: \((V,\mathcal F)\) a set system
Name2: Its hyperedges

Name: A \(k\)-uniform hypergraph
Definition: An hypergraph whose edges are \(k\)-set.
Page: 21
Chapter: 1
Section: 3

Name: A geometric configuration
Definition: A pair \((P,\mathcal L)\) with \(P\) finite and \(\mathcal L\subseteq\mathcal P(P)\) such that, for each \(x,y\in P\), at most one element of \(\mathcal L\) contains \(x\) and \(y\).
Page: 21
Chapter: 1
Section: 3
Definition2: A pair \((P,\mathcal L)\) with \(P\) finite, \(\mathcal L\subseteq\mathcal P(P)\) such that intersection of elements of \(\mathcal L\) is at most a singleton.

Name: A point
Definition: An element of \(P\).
Page: 22
Chapter: 1
Section: 3
Variables: \((P,\mathcal L)\) a geometric configuration

Name: A line
Definition: An element of \(\mathcal L\).
Page: 22
Chapter: 1
Section: 3
Variables: \((P,\mathcal L)\) a geometric configuration

Name: The Fano plane
Definition: .
Page: 22
Chapter: 1
Section: 3
Variables: \((P,\mathcal L)\) a geometric configuration

Name: The Desargues configuration
Definition: .
Page: 22
Chapter: 1
Section: 3

Name: The incidence graph of \((V,\mathcal F)\)
Definition: \(G[V,\mathcal F]\) where \((v,F)\) is an edge if \(v\in F\).
Page: 22
Chapter: 1
Section: 3
Variables: \((V,\mathcal F)\) a set system

Name: The incidence matrix of \((V,\mathcal F)\)
Definition: The bipartite adjacency matrix of the incidence graph of \((V,\mathcal F)\).
Page: 22
Chapter: 1
Section: 3
Variables: \((V,\mathcal F)\) a set system

Name: The Levi graph of \(H\)
Definition: The bipartite adjacency graph of \(H\).
Page: 22
Chapter: 1
Section: 3
Variables: \(H\) a geometric configuration

Name: The Heawod graph
Definition: The bipartite adjacency graph of the Fano Plane,
\(([1,7]\cup\{\ ,'\}, {(x,x'),(x,(x+1)'),(x,(x+3)')})\)
.
Page: 22
Chapter: 1
Section: 3

Name: Its intersection graph
Definition: \(\left(\mathcal F,\{(F,G)\mid F\cap G\ne\emptyset\}\right)\).
Page: 22
Chapter: 1
Section: 3
Variables: \((V,\mathcal F)\) a set system
Context: Set system

Name: The line graph of \(G\)
Definition: The intersection graph of \(G\), considered as a set system.
Page: 23
Chapter: 1
Section: 3
Variables: \(G\) a loopless graph
Abbreviation: \(L(G)\)

Name: An interval graph
Definition: An intersection graph of \((\mathbb R,\mathcal F)\) with \(\mathcal F\) a set of closed intervals.
Page: 23
Chapter: 1
Section: 3

Name: A pencil
Definition: A geometric configuration of the form\((P,\{P\})\).
Page: 27
Chapter: 1
Section: 3
Index: 13
Kind: exercice

Name: A near-pencil
Definition: A geometric configuration of the form \((P\cup\{x\},\{P\}\cup \{P\times\{x\}\})\).
Page: 27
Chapter: 1
Section: 3
Index: 13
Kind: exercice

Name: The Cayley graph of \(\Gamma\) with respect to \(S\)
Definition: Set of vertices: \(\Gamma\)
Page: 28
Chapter: 1
Section: 3
Variables: Les \(\Gamma\) a group,
\(S\subseteq \Gamma\)
Index: 18
Kind: exercice
Definition2: Edges \(\{x,y\}\) for \(xy^{-1}\in S\)
Abbreviation: \(CG(\Gamma,S)\)
Assuming: \(S\) closed under inverse and not containing \(1\)

Name: A circulant
Definition: A Cayley graph \(CG(\mathbb Z_n,S)\) with \(S\subseteq \mathbb Z_n\).
Page: 28
Chapter: 1
Section: 3
Context: graph
Index: 19
Kind: exercice

Name: Paley Graph q
Definition: Set of vertices: \(GF(q)\)
Page: 28
Chapter: 1
Section: 3
Variables: \(q\equiv 1\mod 4\) prime
Index: 20
Kind: exercice
Definition2: Edges: \((x,y)\) when \(x-y\) is a nonzero square
Conjdef: The graph
Abbreviation: \(PG_q\)

Definition: The field of order \(n\)
Page: 28
Chapter: 1
Section: 3
Variables: \(n\in\mathbb N\)
Notation: \(GF(n)\)
Index: 20
Kind: exercice
Assuming: \(n=p^q\) with \(p\) prime, \(q\in\mathbb N\)

Name: Disjoint graphs
Definition: Graphs whose set of vertices are disjoint.
Page: 29
Chapter: 1.4
Section: 41

Name: Edge-disjoint graphs
Definition: Graphs whose set of edges are disjoint.
Page: 29
Chapter: 1.4
Section: 41

Page: 29
Section: 41
Notation: \(\cup\) on graph
Chapter: 1.4
Name: Union of graph
Definition: Sends a set of graphs \(\left(E_i,V_i\right)_{i\in I}\), for \(I\) an index set, to \(\left(\bigcup_{i\in I}E_i,\bigcup_{i\in I}V_i\right)\).
Commutative: commutative
Associative: Associative

Page: 29
Section: 41
Notation: \(+\)
Chapter: 1.4
Name: Disjoint union of graphs
Definition: Sends a set of pairwise disjoint graphs \(\left(E_i,V_i\right)_{i\in I}\) to their union.
Commutative: commutative
Associative: Associative
Context: graph

Name: A connected component of \(G\)
Definition: A connected graph \(H\) such that \(G\) is the disjoint union of \(H\) and some other graphs.
Page: 29
Chapter: 1.4
Section: 41
Variables: \(G\) a graph

Question: The number of sets of disjoint graphs whose disjoint union is \(G\) is
Answer: exactly one.
Page: 29
Chapter: 1.4
Section: 41
Variables: \(G\) a graph

Name: The number of connected components of \(G\)
Page: 29
Chapter: 1.4
Section: 41
Variables: \(G\) a graph
Notation: \(c(G)\)

Page: 30
Section: 41
Notation: \(\square\)
Chapter: 1.4
Name: The Cartesian product
Definition: Set of vertices: \(V(G)\times V(H)\)
Commutative: commutative up to isomorphism
Associative: Associative up to isomorphism
Context: Graph
Definition2: Edges \(((u,v'),(u,v))\),\(((u',v),(u,v))\),\(((u',v'),(u,v'))\) and \(((u',v'),(u',v))\) for \(u\in V(G)\), \(v\in V(G)\) \((u,u')\in E(G)\), \((v,v')\in E(H)\)
ConjDef: Associating \(((V(G),E(G)),(V(H),E(H)))\) to

Name: The \((m\times n)\)-grid
Definition: \(P_m\square P_n\)
Page: 30
Chapter: 1.4
Section: 41
Variables: \(m,n\in\mathbb N\)

Name: The \(n\)-prism
Definition: \(C_n\square K_2\)
Page: 30
Chapter: 1.4
Section: 41
Variables: \(n\in\mathbb N\)

Name: The triangular prism
Definition: The \(3\)-prism
Page: 30
Chapter: 1.4
Section: 41

Name: The cube
Definition: The \(4\)-prism
Page: 30
Chapter: 1.4
Section: 41

Name: The pentagonal prism
Definition: The \(5\)-prism
Page: 30
Chapter: 1.4
Section: 41

Name: A directed graph
Definition: a pair \((V(D),A(D))\) with \(V,A\) disjoint set
Page: 31, 32
Chapter: 1.4
Section: 5
Notation: A diagram of its underlying graph, together with arrows on its edges, each arrow pointing towards the head of the corresponding arc. Two oppositely oriented arcs are represented by an edge
Definition2: \(\psi_D\) sendings elements of \(A(D)\) to ordered pair of not necessarily disjoint elements of \(V(D)\)
Conjdef: A pair with
Abbreviation: A digraph

Name: Its vertices
Definition: The elements of \(V\)
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs

Name: Its arcs
Definition: The elements of \(A\)
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graph

Name: The incidence function
Page: 31
Chapter: 1.4
Section: 5
Variables: \(D=(V,A)\) a directed graphs
Notation: \(\psi_D\)

Name: \(a\) joins \(u\) to \(v\)
Definition: \(\psi_D(a)=(u,v)\).
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs,
\(u,v\) vertices,
\(a\) an arc

Name: A vertex dominated by \(u\)
Definition: A vertex \(v\) such that there exists an arc \((u,v)\).
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs,
\(u\) a vertex,
Name2: An outneighbour of \(u\)

Name: The head of \((u,v)\)
Definition: \(v\).
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs,
\((u,v)\) an arc,

Name: The tail of \((u,v)\)
Definition: \(u\).
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs,
\((u,v)\) an arc,
Context: \((u,v)\) an arc

Name: Its ends
Definition: \(u\) and \(v\).
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs,
\((u,v)\) an arc,

Name: An edge of this graph
Definition: An arc, assuming the order of the ends is irrelevent.
Page: 31
Chapter: 1.4
Section: 5
Variables: \((V,A)\) a directed graphs

Name: The number of arcs
Page: 31
Chapter: 1.4
Section: 5
Variables: \(D=(V,A)\) a directed graphs,
Notation: \(a(D)\)

Name: A vertex dominating \(u\)
Definition: A vertex \(v\) such that there exists an arc \((v,u)\)
Page: 31
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a directed graphs,
\(u\) a vertex
Name2: An inneighbor of \(u\)

Name: The set of in-neighbours of \(u\)
Page: 31
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a directed graphs,
\(u\) a vertex
Notation: \(N^-_D(u)\)

Name: The set of out-neighbours of \(u\)
Page: 31
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a directed graph,
\(u\) a vertex
Notation: \(N^+_D(u)\)

Name: A strict digraph
Definition: loops nor parallel arcs.
Page: 32
Chapter: 1
Section: 5
Definition2: without parallel arcs
Conjdef: A graph

Name: Its underlying graph
Definition: \((V,\{\{u,v\}\mid (u,v)\in A\})\).
Page: 32
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
Notation: \(G(D)\)

Name: Its associated digraph
Definition: \((V,\{(u,v),(v,u)\mid \{u,v\}\in E\})\).
Page: 32
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a graph,
Notation: \(D(G)\)

Name: An orientation of \(G\)
Definition: A digraph of the form \((V,\{(u,v)\mid \{u,v\}\in E\})\) where, for each edge \(\{u,v\}\in E\), only one of the two possible arc is choosen.
Page: 32
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a graph,
Notation: \(\vec G\)

Name: An orientated graph
Definition: \(\vec G\) for some simple graph \(G\).
Page: 32
Chapter: 1
Section: 5

Name: A tournament
Definition: \(\overrightarrow {K_n}\) for some \(n\in\mathbb N\).
Page: 32
Chapter: 1
Section: 5

Name: The indegree of \(v\)
Definition: The number of arcs whose head is \(v\).
Page: 32
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
\(v\in V\)
Notation: \(d^-_D(v)\)

Name: The outdegree of \(v\)
Definition: The number of arcs whose tail is \(v\).
Page: 32
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
\(v\in V\)
Notation: \(d^+_D(v)\)

Name: The minimum indegree
Page: 32
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
\(v\in V\)
Notation: \(\delta^-(D)\)

Name: The minimum outdegree
Page: 32
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
\(v\in V\)
Notation: \(\delta^+(D)\)

Name: The maximum outdegree
Page: 33
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
\(v\in V\)
Notation: \(\Delta^+(D)\)

Name: The maximum indegree
Page: 33
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
\(v\in V\)
Notation: \(\Delta^-(D)\)

Name: A \(k\)-diregular graph
Definition: A graph such that \(\delta^-(D)=\delta^+(D)=\Delta^-(D)=\Delta^+(D)=k\).
Page: 32
Chapter: 1
Section: 5
Variables: \(k\in\mathbb N\)

Name: A source
Definition: A vertex of indegree 0.
Page: 32
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,

Name: A sink
Definition: A vertex of outdegree 0.
Page: 33
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,

Name: A directed path
Definition: An orientation of a path where each vertex dominate its successor.
Page: 33
Chapter: 1
Section: 5

Name: A directed cycle
Definition: An orientation of a cycle where each vertex dominate its successor.
Page: 33
Chapter: 1
Section: 5

Name: The Koh–Tindell digraph
Definition: .
Page: 33
Chapter: 1
Section: 5
Index: 26
Kind: Fig

Name: The Cayley digraph of \(\Gamma\) with respect to \(S\)
Definition: \(\left(\Gamma,\{(x,y)\mid xy^{-1}\in S\}\right)\).
Page: 33
Chapter: 1
Section: 5
Variables: \(G\) a group,
\(S\subseteq G\) not containing \(1\)
Abbreviation: \(CD(\Gamma,S)\)

Name: A directed circulant
Definition: A digraph \(CD(\mathbb Z_n,S)\).
Page: 33
Chapter: 1
Section: 5
Example: The Koh-Tindell digraph, for \(n=7\)

Name: The converse of \(D\)
Definition: \((V,\{(v,u)\mid (u,v)\in A\})\).
Page: 33
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph
Notation: \(\overleftarrow D\)

Name: Principle of Directional Duality
Definition: Any statement about a digraph has an accompanying ‘dual’ statement, obtained by applying the statement to the converse of the digraph and reinterpreting it in terms of the original digraph.
Page: 33
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph

Name: A self converse digraph
Definition: A digraph such that \(G\cong\overleftarrow G\).
Page: 34
Chapter: 1
Section: 5
Kind: Exercice

Name: A balanced digraph
Definition: A digraph \(D\) such that \(|d^+(v)-d^-(v)|\le 1\) for all \(v\in V(D)\).
Page: 35
Chapter: 1
Section: 5
Index: 8
Kind: Exercice

Name: The Paley tournament
Definition: Set of vertices: \(GF(q)\).
Page: 35
Chapter: 1
Section: 5
Variables: \(q\equiv 3\mod 4\) prime
Notation: \(\mathrm{PT}_q\)
Index: 8
Kind: Exercice
Definition2: Edges \((j,i)\) for \(j-i\) a nonzero square

Name: An arc transitive graph
Definition: A graph whose associated digraph is arc-transitive.
Page: 35
Chapter: 1
Section: 5
Index: 12
Kind: Exercice

Name: The square lattice
Definition: The Cartesian product of the two-way infinite path .
Page: 36
Chapter: 1
Section: 6

Name: The triangular lattice
Definition: .
Page: 36
Chapter: 1
Section: 6
Definition2: \((\mathbb Z^2, \{((n,m),(n,m+1)),((n,m),(n+1,m)),((n,m),(n+1,m+1))\mid n,m\in\mathbb Z\} \)

Name: The hexagonal lattice
Definition: vertices \(\mathbb Z^2\)
Page: 36
Chapter: 1
Section: 6
Definition2: edges \((2n,m)\) for \(n,m\in\mathbb Z\)
Conjdef: The graph with
Definition3: edges \((2n,m+1)\) for \(n,m\in\mathbb Z\)
Intuition: .

Name: An infinite path
Definition: A one or two way infinite path.
Page: 36
Chapter: 1
Section: 6

Name: A one-way infinite path
Definition: \((\mathbb N,\{(n,n+1)\mid n\in \mathbb N\})\).
Page: 36
Chapter: 1
Section: 6

Name: A two-way infinite path
Definition: \((\mathbb Z,\{(n,n+1)\mid n\in \mathbb Z\})\).
Page: 36
Chapter: 1
Section: 6
Extra: double

Name: An infinite cycle
Definition: Does not exists, but may be considered to be a two-way infinite path.
Page: 36
Chapter: 1
Section: 6
Context: Graph

Name: The incidence matrix of \(G\)
Definition: The \(V\times A\)-matrix whose \((v,a)\) entry is:
-1 if \(a\) is a link and \(v\) is the tail of \(a\),
-\(-1\) if \(a\) is a link and is \(v\)'s head, and
-0 otherwise.
Page: 34
Chapter: 1
Section: 5
Variables: \(D=(V,A)\) a digraph,
Index: 6
Kind: Exercice

Name: A finite projective plane
Definition: Any two points lie on exactly one line.
Page: 26
Chapter: 1
Section: 3
Index: 13
Kind: exercice
Definition2: Any two lines meet in exactly one point
Conjdef: A geometric configuration \((P,\mathcal L)\) in which
Definition3: There are four points no three of which lie on a line
Extra: finite?
last condition forbids (near)-pencil

Name: The set of automorphism of \(G\)
Page: 16
Chapter: 1
Section: 2
Variables: \(G\) a graph
Abbreviation: \(\text{Aut}(G)\)

Page: 16
Chapter: 1
Section: 2
Name: The automorphism group of \(G\)
Set: The automorphism of \(G\)
Variables: \(G\) a graph
*: Composition
1: Identity morphism
÷: Inverse of automorphism
Abbreviation: \(\text{Aut}(G)\)

Name: A disconnected (di)graph
Definition: A graph \(G=(V,E)\) with a partition \((X,Y)\) of \(V\), such that there is no edge between elements of \(X\) and of \(Y\).
Page: 5, 29
Chapter: 1, 1
Section: 1, 4
Definition2: A disjoint union of two non-null graphs

Smaller0: for all \(xy\in E\in X\times Y\), \(d(x)\ge d(y)\)
Greater0: \(|X|\le |Y|\)
Page: 9
Chapter: 1
Variables: \(G[X,Y]\) a bipartite graph
Index: 3
Kind: Prop
Assuming: \(G\) has no isolated vertices

Page: 12, 34
Definition: The equivalence relation between graphs \(G=(V(G),E(G)),H=(V(H),E(H))\) such that there exists an isomorphism between \(V\) and \(E\).
Chapter: 1, 1
Section: 2, 5
Notation: \(\cong\)
Name: Isomorphic (di)graph
Kind: , exercice
Index: , 3

Name: Similar vertices
Definition: Vertices \(u,v\) such that there is an automorphism of \(G\) sending \(u\) to \(v\)
Page: 15
Chapter: 1
Section: 2
Variables: \(G\) a graph

Page: 32
Definition: two arcs with same head and tail
Chapter: 1
Section: 5
Variables: \((V,A)\) a directed graph
Name: Parallel arcs
Equivalence: equivalence relation