Discussiones Mathematicae Graph Theory 27(3) (2007) 603-610
doi: 10.7151/dmgt.1386

[BIBTex] [PDF] [PS]

MINIMAL NON-SELFCENTRIC RADIALLY-MAXIMAL GRAPHS OF RADIUS 4

Martin Knor

Slovak University of Technology
Faculty of Civil Engineering
Department of Mathematics, Radlinského 11
813 68 Bratislava, Slovakia
e-mail: knor@vox.svf.stuba.sk.

Abstract

There is a hypothesis that a non-selfcentric radially-maximal graph of radius r has at least 3r−1 vertices. Using some recent results we prove this hypothesis for r = 4.

Keywords: non-selfcentric, radially-maximal, critical, center, radius, planar graph.

2000 Mathematics Subject Classification: 05C12.

References

[1] F. Gliviak, M. Knor and L'. Soltés, On radially maximal graphs, Australasian J. Combin. 9 (1994) 275-284.
[2] A. Haviar, P. Hrnciar and G. Monoszová, Eccentric sequences and cycles in graphs, Acta Univ. M. Belii Math. 11 (2004) 7-25.

Received 29 November 2005
Revised 14 August 2006
Accepted 10 January 2007