On critical and cocritical radius edge-invariant graphs

Ondrej Vacek

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 3, page 393-418
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ondrej Vacek. "On critical and cocritical radius edge-invariant graphs." Discussiones Mathematicae Graph Theory 28.3 (2008): 393-418. <http://eudml.org/doc/270696>.

@article{OndrejVacek2008,
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.},
author = {Ondrej Vacek},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {extremal graphs; radius of graph; critical radius edge invariant graph; cocritical radius edge invariant graph},
language = {eng},
number = {3},
pages = {393-418},
title = {On critical and cocritical radius edge-invariant graphs},
url = {http://eudml.org/doc/270696},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Ondrej Vacek
TI - On critical and cocritical radius edge-invariant graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 3
SP - 393
EP - 418
AB - 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.
LA - eng
KW - extremal graphs; radius of graph; critical radius edge invariant graph; cocritical radius edge invariant graph
UR - http://eudml.org/doc/270696
ER -

References

top
  1. [1] V. Bálint and O. Vacek, Radius-invariant graphs, Math. Bohem. 129 (2004) 361-377. Zbl1080.05505
  2. [2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, 1990). Zbl0688.05017
  3. [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. Zbl0820.05020
  4. [4] F. Gliviak, On radially extremal graphs and digraphs, a survey, Math. Bohem. 125 (2000) 215-225. Zbl0963.05072
  5. [5] S.M. Lee, Design of diameter e-invariant networks, Congr. Numer. 65 (1988) 89-102. Zbl0800.05011
  6. [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. Zbl0841.05081
  7. [7] O. Vacek, Diameter-invariant graphs, Math. Bohem. 130 (2005) 355-370. Zbl1112.05033
  8. [8] V.G. Vizing, On the number of edges in graph with given radius, Dokl. Akad. Nauk 173 (1967) 1245-1246 (in Russian). 
  9. [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. Zbl1029.05044

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.