Bigeodetic graphs
type: Item
instance of: scholarly article
title: Bigeodetic graphs
zbMATH Open document ID: 0657.05064
DOI: 10.1007/BF01864174
author: S. H. Smith
published in: Graphs and Combinatorics
publication date: 1988-01-01T00:00:00Z
review text: Geodetic graph is a graph in which every pair of vertices has a unique distance path (the path of minimum length) between them. By relaxing the condition of uniqueness of distance path to at most two distance paths between every pair of vertices, the bigeodetic graph is defined. It is clear that bigeodetic graph is a generalization of geodetic graph and interval-regular graph. In section 2 of this paper the authors describe the structure for a separable graph to be bigeodetic; In Section 3 two necessary and sufficient conditions for a graph to be bigeodetic are given, and other properties of bigeodetic graph are presented; In the last section various bigeodetic graphs are constructed, such as planar bigeodetic block with given girth g and diameter d (d\(\geq \lfloor g/2\rfloor)\), Hamiltonian and Eulerian or non-Hamiltonian and non-Eulerian, and perfect bigeodetic blocks with given diameter \(d\geq 3\). All bigeodetic graphs constructed in this paper are of connectivity 2, the problem of constructing higher connectivity or extremal bigeodetic graphs will be interesting.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4073032
zbMATH Keywords: connectivity
zbMATH Keywords: perfect graph
zbMATH Keywords: Geodetic graph
zbMATH Keywords: distance path
zbMATH Keywords: block
zbMATH Keywords: girth
zbMATH Keywords: bigeodetic graphs
reviewed by: Z. J. Liu
MaRDI profile type: Publication
cites work: Interval-regular graphs of diameter two
cites work: Q4163554
cites work: Q5572939
cites work: Q3291034
cites work: An extremal problem in geodetic graphs
cites work: Geodetic blocks of diameter three
cites work: A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs
cites work: Q4116463
cites work: Geodetic graphs of diameter two
cites work: Q3705483
full work available at URL: https://doi.org/10.1007/bf01864174
OpenAlex ID: W2913444680
Recommended article: Bigraphs and their algebra
Recommended article: Graphoidal bipartite graphs
Recommended article: Bigraphs and transitions
Recommended article: On graphoidal graphs
Recommended article: Bithreshold Graphs
Recommended article: Bithreshold graphs
Recommended article: Q3794212
Recommended article: Betti diagrams from graphs
Recommended article: Q4940013
Recommended article: Q3388527
description: scientific article; zbMATH DE number 4073032