Geodetic graph
In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.
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
[edit]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]
Related graph classes
[edit]
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
[edit]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
[edit]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:
- a block graph in which all the maximal cliques are joined at a single shared vertex, including the windmill graphs,
- a strongly regular graph with parameter (the number of shared neighbors for each nonadjacent pair of vertices) equal to one, or
- a graph with exactly two different vertex degrees.
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]
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]
References
[edit]- ^ a b Ore, Øystein (1962), Theory of Graphs, Colloquium Publications, vol. 38, Providence, Rhode Island: American Mathematical Society, p. 104, ISBN 9780821810385, MR 0150753
- ^ 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
- ^ a b c d "Geodetic graphs", Information System on Graph Classes and their Inclusions, retrieved 2020-09-14
- ^ a b 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
- ^ 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
- ^ Plesník, Ján (1977), "Two constructions of geodetic graphs", Mathematica Slovaca, 27 (1): 65–71, MR 0460179
- ^ 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, vol. 319, pp. 512–517, doi:10.1111/j.1749-6632.1979.tb32829.x, MR 0556062
- ^ a b c 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
- ^ Belousov, I. N.; Makhnev, A. A. (2006), "On strongly regular graphs with and their automorphisms", Doklady Akademii Nauk, 410 (2): 151–155, MR 2455371
- ^ 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
