Graph families

graph that can be embedded in the plane

graph whose vertices can be divided into two disjoint and independent sets

graph where each vertex has the same number of neighbors

graph whose vertices and edges represent the elements of a group and their products with the generators of the group

concept in graph theory

graph in which every vertex is incident to exactly three edges

graph in which all cycles of four or more vertices have a chord

network whose degree distribution follows a power law

mathematical graph where most nodes can be reached by a small number of steps

the unique graph having no vertices

type of graph which admit an automorphism on adjacent vertices

graph in which the number of edges is close to the maximum for its number of vertices

graph with more than k vertices that cannot be disconnected by the deletion of fewer than k vertices

graph in which the number of shared neighbors of two vertices depends only on whether they are adjacent

connected, bridgeless cubic graph with chromatic index equal to 4

sparse graph used in the combinatorics branch of mathematics

graph which is isomorphic to its complement

connected graph in which any two simple cycles have at most one vertex in common

undirected graph in which no three vertices form a triangle of edges

graph whose automorphism group acts transitively upon its vertices

graph whose embedding in a Euclidean space forms a regular tiling

graph where any two nodes of equal distance are isomorphic

regular graph that has as few vertices as possible for its girth

graph that is edge-transitive and regular but not vertex-transitive

undirected graph

graph whose automorphism group acts transitively upon its edges

spectral graph theory concept

largest possible regular graph for its diameter

thumb|The Turán graph T(13,4) is a cograph In graph theory, a cograph, or complement-reducible graph, or '''P4-free graph', is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K''1 and is closed under complementation and disjoint union.

graph which partitions into a clique and independent set

node-link graph for which all eigenvalues of its characteristic polynomial are integers

thumb|The Goldner–Harary graph, an example of a planar 3-tree. In graph theory, a '''k-tree' is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U'' form a clique.

graph that remains connected whenever fewer than k edges are removed

graph whose vertices are or can be partitioned into multiple different independent sets

node-link graph without nontrivial symmetries

recursively-formed graph with two terminal vertices

a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k

graph on at least 3 vertices that remains connected when any one vertex is removed

graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian

special case of a strongly regular graph

undirected graph linking pairs of comparable elements in a partial order

graph that can be drawn without crossings in the plane with all vertices on the outer face

graph that can be made planar by the removal of a single vertex

a type of planar graph formed from a tree by adding a cycle of edges through its leaves

graph that is both vertex-transitive and edge-transitive, but not symmetric

thumb|upright=1.2|A 1-forest (a maximal pseudoforest), formed by three 1-trees In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

graph that contains cycles of all possible lengths from three up to the number of vertices in the graph

graph that can be constructed with a sequence of operations that add either an isolated vertex or a dominating vertex

node-link graph that can be embedded on a torus

family of 7 undirected graphs

graph in which every vertex is incident to exactly four edges

graph with a unique median for each three vertices

graph whose induced subgraphs preserve distance

graph with a prism as its skeleton

undirected graph acted on by a vertex-transitive cyclic group of symmetries

graphs describing the minimally rigid systems of rods and joints in the plane

thumb|A squaregraph. In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face.

connected graph whose biconnected components are all cliques

a type of graph describing the topological structure of the level sets of a real-valued function on a manifold