Bigeodetic graphs (Q1110539): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Z. J. Liu / rank | |||
Property / reviewed by | |||
Property / reviewed by: Z. J. Liu / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Interval-regular graphs of diameter two / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4163554 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3291034 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An extremal problem in geodetic graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geodetic blocks of diameter three / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4116463 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geodetic graphs of diameter two / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3705483 / rank | |||
Normal rank |
Latest revision as of 19:29, 18 June 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
0 references