Graphs (undirected, unlabelled, and simple)

1. Definition

A graph $G = (V,E)$ consists of

We consider graphs to be

2. Examples

The four (undirected, unlabelled, simple) graphs on three vertices $\{0,1,2\}$ are

3. Further Definitions

4. Properties

4.1. Subgraphs

Given graphs $G$ and $H$, $H$ is a subgraph of $G$, notated $H\subseteq G$, if

$H$ is a proper subgraph if either

If $V(H)=V(G)$ but $E(H)\subsetneq E(G)$, then $H$ is a spanning subgraph of $G$.

4.2. Edge Counting Theorem

If $G$ is a graph of size $m$, then $\sum_{v\in V(G)} deg(v) = 2m$

4.3. Eularian Graph Criteria

A nontrivial connected graph $G$ is Eularian if and only if every vertex of G has even degree.

4.4. Four Color Theorem

Every planar graph is four-colorable. That is, the chromatic number of a planar graph is at most four.

5. Remarks

A labeled graph is a graph which has all of its vertices labeled.

A multigraph is a graph in which multiple edges between vertices are allowed as well as loops that connect a vertex to itself.

A directed graph or digraph is a graph in which each edge has a specific orientation or direction.

We have the following 92 statistics in the database:

The number of edges of a graph.
The number of subgraphs.
The number of induced subgraphs.
The length of the maximal independent set of vertices of a graph.
The number of triangles of a graph.
The number of spanning trees of a graph.
The order of the largest clique of the graph.
The chromatic number of a graph.
The degree of the graph.
The Grundy number of a graph.
The cardinality of the automorphism group of a graph.
The burning number of a graph.
The diameter of a connected graph.
The radius of a connected graph.
The edge connectivity of a graph.
The vertex connectivity of a graph.
The Szeged index of a graph.
The girth of a graph, which is not a tree.
The Wiener index of a graph.
The number of spanning subgraphs of a graph with the same connected components.
The number of maximal spanning forests contained in a graph.
The number of strongly connected orientations of a graph.
The number of acyclic orientations of a graph.
The number of forests contained in a graph.
The chromatic index of a connected graph.
The treewidth of a graph.
The domination number of a graph.
The number of perfect matchings of a graph.
The size of the preimage of the map 'to graph' from Ordered trees to Graphs.
The size of the preimage of the map 'to graph' from Binary trees to Graphs.
The number of connected components of the complement of a graph.
The number of connected components of a graph.
The number of nonisomorphic vertex-induced subtrees.
The number of independent sets of vertices of a graph.
The number of facets of the stable set polytope of a graph.
The determinant of the distance matrix of a connected graph.
The determinant of the product of the incidence matrix and its transpose of a gra....
The number of vertices with even degree.
The minimal degree of a vertex of a graph.
The number of vertices of odd degree in a graph.
The number of leaves in a graph.
The number of degree 2 vertices of a graph.
The number of isolated vertices of a graph.
The skewness of a graph.
The minimal crossing number of a graph.
The number of spanning subgraphs of a graph.
The number of strongly connected outdegree sequences of a graph.
The number of different adjacency matrices of a graph.
The sum of the vertex degrees of a graph.
The determinant of the adjacency matrix of a graph.
The second Zagreb index of a graph.
The size of a minimal vertex cover of a graph.
The number of minimal vertex covers of a graph.
The exponent of the automorphism group of a graph.
The Altshuler-Steinberg determinant of a graph.
The genus of a graph.
The number of Hamiltonian cycles in a graph.
The matching number of a graph.
The number of orbits of vertices of a graph under automorphisms.
The Szeged index minus the Wiener index of a graph.
The energy of a graph, if it is integral.
The number of pairs of vertices of a graph with distance 3.
The number of pairs of vertices of a graph with distance 2.
The number of pairs of vertices of a graph with distance 4.
The number of edges minus the number of vertices plus 2 of a graph.
The number of distinct eigenvalues of a graph.
The number of distinct Laplacian eigenvalues of a graph.
The largest eigenvalue of a graph if it is integral.
The second largest eigenvalue of a graph if it is integral.
The monochromatic index of a connected graph.
The Schultz index of a connected graph.
The first Zagreb index of a graph.
The Gutman (or modified Schultz) index of a connected graph.
The hyper-Wiener index of a connected graph.
The Hosoya index of a graph.
The distinguishing number of a graph.
The Ramsey number of a graph.
The (zero)-forcing number of a graph.
The rank-width of a graph.
The pathwidth of a graph.
The cutwidth of a graph.
The cop number of a graph.
The number of cut vertices of a graph.
The number of blocks of a connected graph.
The F-index (or forgotten topological index) of a graph.
The hull number of a graph.
The length of the longest cycle in a graph.
The maximin edge-connectivity for choosing a subgraph.
The toughness times the least common multiple of 1,.
The largest Laplacian eigenvalue of a graph if it is integral.
The number of different neighbourhoods in a graph.
The maximal cardinality of a set of vertices with the same neighbourhood in a gra....

6. Maps

We have the following 3 maps in the database:

to partition of connected components
complement
Ore closure

7. References

8. Sage examples


CategoryCombinatorialCollection

Graphs (last edited 2016-05-30 11:33:50 by ChristianStump)