ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 28(3) (2008) 393-418
DOI: 10.7151/dmgt.1415


Ondrej Vacek

Department of Mathematics and Descriptive Geometry
Faculty of Wood Sciences and Technology
Technical University Zvolen
T.G. Masaryka 24, 960 53 Zvolen, Slovak Republic


The concepts of critical and cocritical radius edge-invariant graphs are introduced. We prove that every graph can be embedded as an induced subgraph of a critical or cocritical radius-edge-invariant graph. We show that every cocritical radius-edge-invariant graph of radius r ≥ 15 must have at least 3r+2 vertices.

Keywords: extremal graphs, radius of graph.

2000 Mathematics Subject Classification: 05C12, 05C35.


[1] V. Bálint and O. Vacek, Radius-invariant graphs, Math. Bohem. 129 (2004) 361-377.
[2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, 1990).
[3] R.D. Dutton, S.R. Medidi and R.C. Brigham, Changing and unchanging of the radius of graph, Linear Algebra Appl. 217 (1995) 67-82, doi: 10.1016/0024-3795(94)00153-5.
[4] F. Gliviak, On radially extremal graphs and digraphs, a survey, Math. Bohem. 125 (2000) 215-225.
[5] S.M. Lee, Design of diameter e-invariant networks, Congr. Numer. 65 (1988) 89-102.
[6] S.M. Lee and A.Y. Wang, On critical and cocritical diameter edge-invariant graphs, Graph Theory, Combinatorics, and Applications 2 (1991) 753-763.
[7] O. Vacek, Diameter-invariant graphs, Math. Bohem. 130 (2005) 355-370.
[8] V.G. Vizing, On the number of edges in graph with given radius, Dokl. Akad. Nauk 173 (1967) 1245-1246 (in Russian).
[9] H.B. Walikar, F. Buckley and K.M. Itagi, Radius-edge-invariant and diameter-edge-invariant graphs, Discrete Math. 272 (2003) 119-126, doi: 10.1016/S0012-365X(03)00189-4.

Received 11 September 2006
Revised 18 December 2007
Accepted 6 June 2008