Network Fact

Complex networks johndcook.com/blog/complex-n…

The degree matrix of a graph is a diagonal matrix whose ii-th entry is the degree of the ith node.

A simple graph is an undirected graph with no edges from a vertex to itself and no more than one edge between different vertices.

Six degrees of Kevin Bacon, Paul Erdos, and Wikipedia johndcook.com/blog/2018/12/0…

A flow network is a directed graph in which each edge (u, v) has an associated capacity c(u, v) >= 0.

Breadth-first search runs in time linear in the size of the adjacenty-list representation of a graph.

In many real-world networks, average distances are on the order of the log of the number of vertices.

Two nodes x and y in a directed graph are strongly connected if there is a path from x to y and a path from y to x.

Visualizing correlations with graphs johndcook.com/blog/2022/09/2…

Two nodes x and y in a directed graph are weakly connected if there is a path from x to y or from y to x.

Gallery of named graphs altermundus.fr/downloads/doc… // 104-page pdf from Alain Matthes

A connected graph contains an Eulerian path iff there are zero or two nodes of odd degree.

Shortest tours of Eurasia and Oceania johndcook.com/blog/2022/09/0…

A Hamiltonian path visits each vertex in a graph exactly once.

An Eulerian path traverses each edge in a graph exactly once.

Some authors say graph theory started with Euler's solution to the Kӧnigsberg bridge problem in 1736.

The diameter of a connected graph is the length of the longest geodesic path in the graph.

Graphviz - Graph Visualization Software graphviz.org/

If A is the adjacency matrix of a graph, the number of walks from i to j of length r is the ij-th entry of A^r.

The density of a graph is the ratio of the actual number of edges to the maximum possible number of edges.

The degree of a vertex is the number of edges connected to it.