On the connectivity and diameter of geodetic graphs

DOI10.1016/J.EJC.2023.103886arXiv2208.06324OpenAlexW4388838939MaRDI QIDQ6189693FDOQ6189693

Authors: Asaf Etgar, Nathan Linial 

Publication date: 5 February 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A graph $G$ is geodetic if between any two vertices there exists a unique shortest path. In 1962 Ore raised the challenge to characterize geodetic graphs, but despite many attempts, such characterization still seems well beyond reach. We may assume, of course, that $G$ is $2$-connected, and here we consider only graphs with no vertices of degree $1$ or $2$. We prove that all such graphs are, in fact $3$-connected. We also construct an infinite family of such graphs of the largest known diameter, namely $5$.

Full work available at URL: https://arxiv.org/abs/2208.06324

Recommendations

• scientific article; zbMATH DE number 4208114
• Geodetic graphs of diameter two
• An extremal problem in geodetic graphs
• A new upper bound on the number of edges in a geodetic graph
• On the geodetic number of a graph

zbMATH Keywords

self-centered graphsgeodetic block

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Cites Work

• A course in combinatorics.
• Title not available (Why is that?)
• New proof of a characterization of geodetic graphs
• Geodetic graphs of diameter two
• Even-hole-free graphs: A survey
• Geodetic graphs of diameter two
• Geodetic blocks of diameter three
• On planar geodetic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geodetic graphs of diameter two and some related structures
• Title not available (Why is that?)
• Rewriting systems, plain groups, and geodetic graphs

Cited In (1)

• On graphs with unique geoodesics and antipodes

This page was built for publication: On the connectivity and diameter of geodetic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6189693)