Half-square on:
[Wikipedia]
[Google]
[Amazon]
In
In graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the bipartite half or half-square of a bipartite graph is a graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
whose vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
set is one of the two sides of the bipartition (without loss of generality
''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicat ...
, ) and in which there is an edge for each pair of vertices in that are at distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
two from each other in . That is, in a more compact notation, the bipartite half is where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
.
Examples
For instance, the bipartite half of thecomplete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
is the complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
and the bipartite half of the hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, e ...
is the halved cube graph
In graph theory, the halved cube graph or half cube graph of dimension is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square o ...
.
When is a distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .
...
, its two bipartite halves are both distance-regular. For instance, the halved Foster graph
In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.
The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is ...
is one of finitely many degree-6 distance-regular locally linear graph
In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be ...
s.
Representation and hardness
Every graph is the bipartite half of another graph, formed by subdividing the edges of into two-edge paths. More generally, a representation of as a bipartite half can be found by taking any clique edge cover of and replacing each clique by a star. Every representation arises in this way. Since finding the smallest clique edge cover is NP-hard, so is finding the graph with the fewest vertices for which is the bipartite half.Special cases
The map graphs, that is, theintersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
s of interior-disjoint simply-connected regions in the plane, are exactly the bipartite halves of bipartite planar graphs..
See also
*Bipartite double cover
In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, cano ...
References
{{reflist Graph operations Bipartite graphs