On critical and cocritical radius edge-invariant graphs
Ondrej Vacek
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 393-418 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270696 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1415,
     author = {Ondrej Vacek},
     title = {On critical and cocritical radius edge-invariant graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {393-418},
     zbl = {1173.05017},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1415}
}

Ondrej Vacek. On critical and cocritical radius edge-invariant graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 393-418. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1415/

[000] [1] V. Bálint and O. Vacek, Radius-invariant graphs, Math. Bohem. 129 (2004) 361-377. | Zbl 1080.05505

[001] [2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, 1990). | Zbl 0688.05017

[002] [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. | Zbl 0820.05020

[003] [4] F. Gliviak, On radially extremal graphs and digraphs, a survey, Math. Bohem. 125 (2000) 215-225. | Zbl 0963.05072

[004] [5] S.M. Lee, Design of diameter e-invariant networks, Congr. Numer. 65 (1988) 89-102. | Zbl 0800.05011

[005] [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. | Zbl 0841.05081

[006] [7] O. Vacek, Diameter-invariant graphs, Math. Bohem. 130 (2005) 355-370. | Zbl 1112.05033

[007] [8] V.G. Vizing, On the number of edges in graph with given radius, Dokl. Akad. Nauk 173 (1967) 1245-1246 (in Russian).

[008] [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. | Zbl 1029.05044