Graph isomorphisms, automorphisms and graph complements

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
• Injection, surjection, bijection

Used by

• A c-sparse set X satisfies α(G[X])≥|X|/(c|X|+1), and a c-dense set satisfies ω(G[X])≥|X|/(c|X|+1) Corollary
• An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree Corollary
• Every graph on at most three vertices has the Erdős–Hajnal property Corollary
• Few induced copies force a linearly large induced subgraph with bounded maximum degree Corollary
• G is H-free if and only if Ḡ is H̄-free Corollary
• The prime quotient produced by the modular decomposition of a connected and anticonnected graph has at least four vertices Corollary
• The singleton family {E} has property (*) Corollary
• The star-expansion of the four-vertex path and its complement have the Erdős-Hajnal property Corollary
• C₆ and the disjoint union of two triangles have the same degree sequence but are not isomorphic Counterexample
• A nice graph Definition
• A split set in a bull-free graph Definition
• Anticonnected graphs and anticonnected components Definition
• c-sparse, c-dense and c-restricted vertex sets Definition
• Co-leaves of a finite graph Definition
• Generalized nice finite graph families Definition
• Hereditary graph classes Definition
• Holes, antiholes, and odd holes Definition
• Induced embeddings and induced copies of a graph Definition
• Labelled directed graphs, their underlying simple graphs, and label-preserving isomorphisms Definition
• Property (*) for a finite graph family Definition
• Substituting one graph for a vertex of another Definition
• The complement of a graph class Definition
• The right six-vertex prime H-graph Definition
• The star-expansion of a graph Definition
• The structural comb-partition hypothesis Definition
• Wonderful finite graph families Definition
• A co-leaf of P₅ is exactly a leaf of P₅ Example
• P₄ is both connected and anticonnected Example
• R(3,3)=6 in both directions: the six-vertex argument and the red 5-cycle whose blue complement is another 5-cycle Example
• The Bird graph and co-Bird by finite adjacency data Example
• The bull graph is self-complementary Example
• The E-graph and co-E by finite adjacency data Example
• The isomorphism types of trees on at most five vertices Example
• The right six-vertex prime H-graph is the complement of the left one, and is prime Example
• The self-complementary five-cycle satisfies hom(C₅)=2 Example
• Up to isomorphism the four-vertex path is the only prime graph on four vertices Example
• FALSE: a finite simple graph is determined up to isomorphism by its degree sequence False statement
• FALSE: groups with isomorphic Cayley graphs are isomorphic False statement
• A bijection of vertex sets is an isometry for the path metrics if and only if it is a graph isomorphism Lemma
• A quotient block of connected or anticonnected blocks is again connected or anticonnected Lemma

…and 30 more results.

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

• R. Diestel, Graph Theory, Chapter 1 preview (standard reference, not scraped)