On critical and cocritical radius edge-invariant graphs

Ondrej Vacek

ArticleOriginal scientific text

Title

On critical and cocritical radius edge-invariant graphs

Authors ¹

Affiliations

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

Abstract

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

ENG

extremal graphs, radius of graph

V. Bálint and O. Vacek, Radius-invariant graphs, Math. Bohem. 129 (2004) 361-377.
F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, 1990).
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.
F. Gliviak, On radially extremal graphs and digraphs, a survey, Math. Bohem. 125 (2000) 215-225.
S.M. Lee, Design of diameter e-invariant networks, Congr. Numer. 65 (1988) 89-102.
S.M. Lee and A.Y. Wang, On critical and cocritical diameter edge-invariant graphs, Graph Theory, Combinatorics, and Applications 2 (1991) 753-763.
O. Vacek, Diameter-invariant graphs, Math. Bohem. 130 (2005) 355-370.
V.G. Vizing, On the number of edges in graph with given radius, Dokl. Akad. Nauk 173 (1967) 1245-1246 (in Russian).
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.

Title

On critical and cocritical radius edge-invariant graphs

Affiliations

Abstract

Keywords

Bibliography