Bigeodetic graphs (Q1110539): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q180312 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Z. J. Liu / rank | |||
Normal rank |
Revision as of 13:14, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bigeodetic graphs |
scientific article |
Statements
Bigeodetic graphs (English)
0 references
1988
0 references
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.
0 references
connectivity
0 references
perfect graph
0 references
Geodetic graph
0 references
distance path
0 references
block
0 references
girth
0 references
bigeodetic graphs
0 references