Modular graph

Not to be confused with Modular decomposition or Modularity (networks).
A modular graph derived from a modular lattice

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). In this case, the only vertices on the shortest path yz are y and z themselves. Neither can belong to a shortest path from x to the other without shortcutting C and creating a shorter odd cycle. Because they have no odd cycles, 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]

References

  1. ^ a b c d Modular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
  2. ^ a b 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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.