In graph theory, the sphericity of a graph is a graph invariant defined to be the smallest dimension of Euclidean space required to realize the graph as an intersection graph of unit spheres. The sphericity of a graph is a generalization of the boxicity and cubicity invariants defined by F.S. Roberts in the late 1960s. [1] [2] The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s. [3]
Let be a graph. Then the sphericity of , denoted by , is the smallest integer such that can be realized as an intersection graph of unit spheres in -dimensional Euclidean space . [4]
Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in some -dimensional Euclidean space, a space graph is built by connecting pairs of points with a line segment when their Euclidean distance is less than some specified constant. Then the sphericity of a graph is the minimum such that is isomorphic to a space graph in . [3]
Graphs of sphericity 1 are known as interval graphs or indifference graphs. Graphs of sphericity 2 are known as unit disk graphs.
The sphericity of certain graph classes can be computed exactly. The following sphericities were given by Maehara on page 56 of his original paper on the topic.
| Graph | Description | Sphericity | Notes |
|---|---|---|---|
| Complete graph | 0 | ||
| Complete graph | 1 | ||
| Path graph | 1 | ||
| Circuit graph | 2 | ||
| Complete m-partite graph on m sets of size 2 | 2 |
The most general known upper bound on sphericity is as follows. Assuming the graph is not complete, then where is the clique number of and denotes the number of vertices of [3]
In mathematics, the isoperimetric inequality is a geometric inequality involving the square of the circumference of a closed curve in the plane and the area of a plane region it encloses, as well as its various generalizations. Isoperimetric literally means "having the same perimeter". Specifically, the isoperimetric inequality states, for the length L of a closed curve and the area A of the planar region that it encloses, that
In geometry, the Dehn invariant is a value used to determine whether one polyhedron can be cut into pieces and reassembled ("dissected") into another, and whether a polyhedron or its dissections can tile space. It is named after Max Dehn, who used it to solve Hilbert's third problem by proving that certain polyhedra with equal volume cannot be dissected into each other.
In mathematics, a volume form or top-dimensional form is a differential form of degree equal to the differentiable manifold dimension. Thus on a manifold of dimension , a volume form is an -form. It is an element of the space of sections of the line bundle , denoted as . A manifold admits a nowhere-vanishing volume form if and only if it is orientable. An orientable manifold has infinitely many volume forms, since multiplying a volume form by a nowhere-vanishing real valued function yields another volume form. On non-orientable manifolds, one may instead define the weaker notion of a density.
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
In geometry, the Beckman–Quarles theorem states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. The theorem is named after Frank S. Beckman and Donald A. Quarles Jr., who published this result in 1953; it was later rediscovered by other authors and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.
In graph theory, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the voltage graph.
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
In graph theory, a starSk is the complete bipartite graph K1,k : a tree with one internal node and k leaves. Alternatively, some authors define Sk to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves.
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte that every cubic 3-connected bipartite graph is Hamiltonian. The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2.
In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.
In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.
In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph, or a disjoint union of nontrivial paths. Equivalently, it is an acyclic and claw-free graph. An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest. An undirected graph has Colin de Verdière graph invariant at most 1 if and only if it is a (node-)disjoint union of paths, i.e. it is linear. Any linear forest is a subgraph of the path graph with the same number of vertices.
Paul Allen Catlin was a mathematician, professor of mathematics who worked in graph theory and number theory. He wrote a significant paper on the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.
In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if is a 2-vertex-connected graph, then the square of is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974.
A dot product representation of a simple graph is a method of representing a graph using vector spaces and the dot product from linear algebra. Every graph has a dot product representation.
In geometry, a valuation is a finitely additive function from a collection of subsets of a set to an abelian semigroup. For example, Lebesgue measure is a valuation on finite unions of convex bodies of Other examples of valuations on finite unions of convex bodies of are surface area, mean width, and Euler characteristic.
In mathematics, and especially differential geometry and mathematical physics, gauge theory is the general study of connections on vector bundles, principal bundles, and fibre bundles. Gauge theory in mathematics should not be confused with the closely related concept of a gauge theory in physics, which is a field theory which admits gauge symmetry. In mathematics theory means a mathematical theory, encapsulating the general study of a collection of concepts or phenomena, whereas in the physical sense a gauge theory is a mathematical model of some natural phenomenon.
In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.
A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.
In graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as an intersection graph of unit cubes in Euclidean space. Cubicity was introduced by Fred S. Roberts in 1969 along with a related invariant called boxicity that considers the smallest dimension needed to represent a graph as an intersection graph of axis-parallel rectangles in Euclidean space.
