Modular graph

Last updated July 23, 2023

In graph theory, a branch of mathematics, the modular graphs are undirected graphs in which every three vertices $x$ , $y$ , and $z$ have at least one median vertex $m (x, y, z)$ that belongs to shortest paths between each pair of $x$ , $y$ , and $z$ .^[1] Their name comes from the fact that a finite lattice is a modular lattice if and only if its Hasse diagram is a modular graph.^[2]

It is not possible for a modular graph to contain a cycle of odd length. For, if $C$ is a shortest odd cycle in a graph, $x$ is a vertex of $C$ , and $yz$ is the edge of $C$ farthest from $x$ , there could be no median $m (x, y, z)$ , for the only vertices on the shortest path $yz$ are $y$ and $z$ themselves, but neither can belong to a shortest path from $x$ to the other without shortcutting $C$ and creating a shorter odd cycle. Therefore, every modular graph is a bipartite graph.^[1]

The modular graphs contain as a special case the median graphs, in which every triple of vertices has a unique median;^[1] median graphs are related to distributive lattices in the same way that modular graphs are related to modular lattices. However, the modular graphs also include other graphs such as the complete bipartite graphs where the medians are not unique: when the three vertices $x$ , $y$ , and $z$ all belong to one side of the bipartition of a complete bipartite graph, every vertex on the other side is a median.^[2] Every chordal bipartite graph (a class of graphs that includes the complete bipartite graphs and the bipartite distance-hereditary graphs) is modular.^[1]

Related Research Articles

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete.

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

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.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In mathematics, a median algebra is a set with a ternary operation $satisfying a set of axioms which generalise the notions of medians of triples of real numbers and of the Boolean majority function.$

<span class="mw-page-title-main">Squaregraph</span> Planar graph with quadrilateral faces

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.

In graph theory, a branch of mathematics, the simplex graph $κ(G)$ of an undirected graph $G$ is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in $G$ . Two nodes of $κ(G)$ are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.

References

1 2 3 4 Modular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
1 2 Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", Discrete Applied Mathematics , 16 (3): 191–215, doi: 10.1016/0166-218X(87)90058-8 , MR 0878021 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[isgci-1] 1 2 3 4 Modular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

[arb-2] 1 2 Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", Discrete Applied Mathematics , 16 (3): 191–215, doi: 10.1016/0166-218X(87)90058-8 , MR 0878021 .

[1]

[2]