blob: b3d318fda316f54d58b3d0466e9cbf4fec3dfbf8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
%This macro provides the math text for the second column of page 5
%
%The macro has one parameter:
% 1) The width of the text
\newcommand\TFiveGrapheOne[1]{%
\def\LineOfArray##1##2{##1&{\raggedright ##2}\\}
\parbox[t]{#1}{%
%Space dedicated to the explanation of the graph's
%vocabulary in the tabular environment
\deflength{\HSpace}{.70#1}
\TFiveGraphFontSize
%Since the column is narrow, ragged at right
%produces better spacing
%
\raggedright
\TFiveTitle{Definitions:}
\begin{tabular}{@{}l@{\hspace{.25em}}p{\HSpace}}
\LineOfArray{Loop}{An edge connecting a vertex to itself.}
\LineOfArray{Directed}{Each edge has a direction.}
\LineOfArray{Simple}{Graph with no loops or multi-edges.}
\LineOfArray{Walk}{A sequence $v_0e_1v_1\ldots e_\ell v_\ell$.}
\LineOfArray{Trail}{A walk with distinct edges.}
\LineOfArray{Path}{A trail with distinct vertices.}
\LineOfArray{Connected}{A graph where there exists a path between any two vertices.}
\LineOfArray{Component}{A maximal connected subgraph.}
\LineOfArray{Tree}{A connected acyclic graph.}
\LineOfArray{Free tree}{A tree with no root.}
\LineOfArray{DAG}{Directed acyclic graph.}
\LineOfArray{Eulerian}{Graph with a trail visiting each edge exactly once.}
\LineOfArray{Hamiltonian}{Graph with a cycle visiting each vertex exactly once.}
\LineOfArray{Cut}{A set of edges whose removal increases the number of components.}
\LineOfArray{Cut-set}{A minimal cut.}
\LineOfArray{Cut edge}{A size 1 cut.}
\LineOfArray{k-Connected}{A graph connected with the removal of any $k-1$ vertices.}
\LineOfArray{k-Tough}{$\forall S \subseteq V, S \neq \emptyset$ we have $k\cdot c(G-S) \leq \vert S \vert$.}
\LineOfArray{k-Regular}{A graph where all vertices have degree $k$.}
\LineOfArray{k-Factor}{A $k$-regular spanning subgraph.}
\LineOfArray{Matching}{A set of edges, no two of which are adjacent.}
\LineOfArray{Clique}{A set of vertices, all of which are adjacent.}
\LineOfArray{Ind. set}{A set of vertices, none of which are adjacent.}
\LineOfArray{Vertex cover}{A set of vertices which cover all edges.}
\LineOfArray{Planar graph}{A graph which can be embeded in the plane.}
\LineOfArray{Plane graph}{An embedding of a planar graph.}
\end{tabular}
\TFiveTitle{Planar graphs}
\AdjustSpace{1ex plus .5ex minus .2ex}
\begin{DisplayFormulae}{1}{0pt}{4ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
\Fm{\sum_{v\in V} \deg(v) = 2 m}
\end{DisplayFormulae}
\AdjustSpace{1ex plus .5ex minus .2ex}
If $G$ is planar then $n - m + f = 2$, so
\AdjustSpace{1ex plus .5ex minus .2ex}
\begin{DisplayFormulae}{1}{0pt}{4ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
\Fm{f \leq 2n - 4, \quad m \leq 3 n - 6}
\end{DisplayFormulae}
\AdjustSpace{1ex plus .5ex minus .2ex}
Any planar graph has a vertex with degree $\leq 5$.
\TFiveTitle{Notation:}
\begin{tabular}{@{}lp{\HSpace}}
\LineOfArray{$E(G)$}{Edge set}
\LineOfArray{$V(G)$}{Vertex set}
\LineOfArray{$c(G)$}{Number of components}
\LineOfArray{$G[S]$}{Induced subgraph}
\LineOfArray{$\deg(v)$}{Degree of $v$}
\LineOfArray{$\Delta(G)$}{Maximum degree}
\LineOfArray{$\delta(G)$}{Minimum degree}
\LineOfArray{$\chi(G)$}{Chromatic number}
\LineOfArray{$\chi_E(G)$}{Edge chromatic number}
\LineOfArray{$G^c$}{Complement graph}
\LineOfArray{$K_n$}{Complete graph}
\LineOfArray{$K_{n_1,n_2}$}{Complete bipartite graph}
\LineOfArray{$\ramsey(k,\ell)$}{Ramsey number}
\end{tabular}
}
}
|