Geodetic graph

Last updated

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

Contents

Geodetic graphs were introduced in 1962 by Øystein Ore, who observed that they generalize a property of trees (in which there exists a unique path between each two vertices regardless of distance), and asked for a characterization of them. [1] Although these graphs can be recognized in polynomial time, "more than sixty years later a full characterization is still elusive". [2]

Examples

Every tree, [1] every complete graph, [3] and every odd-length cycle graph is geodetic. [4]

If is a geodetic graph, then replacing every edge of by a path of the same odd length will produce another geodetic graph. [5] In the case of a complete graph, a more general pattern of replacement by paths is possible: choose a non-negative integer for each vertex , and subdivide each edge by adding vertices to it. Then the resulting subdivided complete graph is geodetic, and every geodetic subdivided complete graph can be obtained in this way. [6] [7]

A block graph, a special case of a geodetic graph Block graph.svg
A block graph, a special case of a geodetic graph
The Petersen graph, one of the geodetic graphs of diameter two Petersen1 tiny.svg
The Petersen graph, one of the geodetic graphs of diameter two

If every biconnected component of a graph is geodetic then the graph itself is geodetic. In particular, every block graph (graphs in which the biconnected components are complete) is geodetic. [3] Similarly, because a cycle graph is geodetic when it has odd length, every cactus graph in which the cycles have odd length is also geodetic. These cactus graphs are exactly the connected graphs in which all cycles have odd length. More strongly, a planar graph is geodetic if and only if all of its biconnected components are either odd-length cycles or geodetic subdivisions of a four-vertex clique. [4]

Computational complexity

Geodetic graphs may be recognized in polynomial time, by using a variation of breadth first search that can detect multiple shortest paths, starting from each vertex of the graph. Geodetic graphs cannot contain an induced four-vertex cycle graph, nor an induced diamond graph, because these two graphs are not geodetic. [3] In particular, as a subset of diamond-free graphs, the geodetic graphs have the property that every edge belongs to a unique maximal clique; in this context, the maximal cliques have also been called lines. [8] It follows that the problem of finding maximum cliques, or maximum weighted cliques, can be solved in polynomial time for geodetic graphs, by listing all maximal cliques. The broader class of graphs that have no induced 4-cycle or diamond are called "weakly geodetic"; these are the graphs where vertices at distance exactly two from each other have a unique shortest path. [3]

Diameter two

For graphs of diameter two (that is, graphs in which all vertices are at distance at most two from each other), the geodetic graphs and weakly geodetic graphs coincide. Every geodetic graph of diameter two is of one of three types:

The strongly regular geodetic graphs include the 5-vertex cycle graph, the Petersen graph, and the Hoffman–Singleton graph. Despite additional research on the properties such a graph must have, [9] [10] it is not known whether there are more of these graphs, or infinitely many of these graphs. [8]

Unsolved problem in mathematics:

Are there infinitely many strongly regular geodetic graphs?

(more unsolved problems in mathematics)

Geodetic graphs with diameter two and two different degrees cannot have a triangle composed of vertices of both degrees. They can be constructed from any finite affine plane by adding to the point-line incidence graph of the plane additional edges between the vertices corresponding to each two parallel lines. For the binary affine plane with four points and six two-point lines in three parallel pairs, the result of this construction is the Petersen graph, but for higher-order finite affine planes it produces graphs with two different degrees. Other related constructions of geodetic graphs from finite geometries are also known, but it is not known whether these exhaust all the possible geodetic graphs with diameter two and two different degrees. [8]

Related Research Articles

Petersen graph Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

Hamiltonian path Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

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 discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

Edge coloring

In graph theory, an 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.

Chordal graph Graph family

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

Peripheral cycle

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

Distance-hereditary graph

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 graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

Hamiltonian decomposition

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

Pancyclic graph

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.

Block graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

Well-covered graph

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which every maximal independent set has the same size. Well-covered graphs were defined and first studied by Plummer (1970).

Skew partition

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

Ptolemaic graph

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

References

  1. 1 2 Ore, Øystein (1962), Theory of Graphs, Colloquium Publications, 38, Providence, Rhode Island: American Mathematical Society, p. 104, ISBN   9780821810385, MR   0150753
  2. ↑ Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; Gronemann, Martin; Hoffmann, Michael; Kobourov, Stephen; Schneck, Thomas (2020), "Drawing shortest paths in geodetic graphs", Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization, arXiv: 2008.07637
  3. 1 2 3 4 "Geodetic graphs", Information System on Graph Classes and their Inclusions, retrieved 2020-09-14
  4. 1 2 Stemple, Joel G.; Watkins, Mark E. (1968), "On planar geodetic graphs", Journal of Combinatorial Theory , 4 (2): 101–117, doi: 10.1016/S0021-9800(68)80035-3 , MR   0218267
  5. ↑ Parthasarathy, K. R.; Srinivasan, N. (1982), "Some general constructions of geodetic blocks", Journal of Combinatorial Theory , Series B, 33 (2): 121–136, doi: 10.1016/0095-8956(82)90063-6 , MR   0685061
  6. ↑ Plesník, Ján (1977), "Two constructions of geodetic graphs", Mathematica Slovaca, 27 (1): 65–71, MR   0460179
  7. ↑ Stemple, Joel G. (1979), "Geodetic graphs homeomorphic to a complete graph", Second International Conference on Combinatorial Mathematics (New York, 1978), Annals of the New York Academy of Sciences, 319, pp. 512–517, doi:10.1111/j.1749-6632.1979.tb32829.x, MR   0556062
  8. 1 2 3 Blokhuis, A.; Brouwer, A. E. (1988), "Geodetic graphs of diameter two", Geometriae Dedicata , 25 (1–3): 527–533, doi:10.1007/BF00191941, MR   0925851, S2CID   189890651
  9. ↑ Belousov, I. N.; Makhnev, A. A. (2006), "On strongly regular graphs with and their automorphisms", Doklady Akademii Nauk , 410 (2): 151–155, MR   2455371
  10. ↑ Deutsch, J.; Fisher, P. H. (2001), "On strongly regular graphs with ", European Journal of Combinatorics , 22 (3): 303–306, doi: 10.1006/eujc.2000.0472 , MR   1822718
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.