Geodesic
Diameter-invariant graphs
Mathematica Bohemica, Tome 130 (2005) no. 4, pp. 355-370

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
The diameter of a graph $G$ is the maximal distance between two vertices of $G$. A graph $G$ is said to be diameter-edge-invariant, if $d(G-e)=d(G)$ for all its edges, diameter-vertex-invariant, if $d(G-v)=d(G)$ for all its vertices and diameter-adding-invariant if $d(G+e)=d(e)$ for all edges of the complement of the edge set of $G$. This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.
The diameter of a graph $G$ is the maximal distance between two vertices of $G$. A graph $G$ is said to be diameter-edge-invariant, if $d(G-e)=d(G)$ for all its edges, diameter-vertex-invariant, if $d(G-v)=d(G)$ for all its vertices and diameter-adding-invariant if $d(G+e)=d(e)$ for all edges of the complement of the edge set of $G$. This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.
DOI : 10.21136/MB.2005.134211
Classification : 05C12, 05C35
Keywords: extremal graphs; diameter of graph; distance 
Vacek, Ondrej. Diameter-invariant graphs. Mathematica Bohemica, Tome 130 (2005) no. 4, pp. 355-370. doi: 10.21136/MB.2005.134211
@article{10_21136_MB_2005_134211,
     author = {Vacek, Ondrej},
     title = {Diameter-invariant graphs},
     journal = {Mathematica Bohemica},
     pages = {355--370},
     year = {2005},
     volume = {130},
     number = {4},
     doi = {10.21136/MB.2005.134211},
     mrnumber = {2182382},
     zbl = {1112.05033},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134211/}
}
TY  - JOUR
AU  - Vacek, Ondrej
TI  - Diameter-invariant graphs
JO  - Mathematica Bohemica
PY  - 2005
SP  - 355
EP  - 370
VL  - 130
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134211/
DO  - 10.21136/MB.2005.134211
LA  - en
ID  - 10_21136_MB_2005_134211
ER  - 
%0 Journal Article
%A Vacek, Ondrej
%T Diameter-invariant graphs
%J Mathematica Bohemica
%D 2005
%P 355-370
%V 130
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134211/
%R 10.21136/MB.2005.134211
%G en
%F 10_21136_MB_2005_134211

[1] V. Bálint, O. Vacek: Radius-invariant graphs. Math. Bohem. 129 (2004), 361–377. | MR

[2] F. Buckley, F. Harary: Distance in Graphs. Addison-Wesley, Redwood City, 1990. | MR

[3] R. D. Dutton, S. R. Medidi, R. C. Brigham: Changing and unchanging of the radius of graph. Linear Algebra Appl. 217 (1995), 67–82. | MR

[4] R. Frucht, F. Harary: On the corona of two graphs. Aequationes Math. 4 (1970), 322–325. | DOI | MR

[5] F. Gliviak: On radially extremal graphs and digraphs, a survey. Math. Bohem. 125 (2000), 215–225. | MR | Zbl

[6] F. Glivjak: On certain classes of graphs of diameter two without superfluous edges. Acta Fac. Rer. Nat. Univ. Comenianae, Math. 21 (1968), 39–48. | MR

[7] F. Glivjak, P. Kyš, J. Plesník: On the extension of graphs with a given diameter without superfluous edges. Mat. Cas. Slovensk. Akad. Vied 19 (1969), 92–101. | MR

[8] N. Graham, F. Harary: Changing and unchanging the diameter of a hypercube. Discrete Appl. Math. 37/38 (1992), 265–274. | MR

[9] F. Harary: Changing and unchanging invariants for graphs. Bull Malaysian Math. Soc. 5 (1982), 73–78. | MR | Zbl

[10] S. M. Lee: Design of diameter $e$-invariant networks. Congr. Numerantium 65 (1988), 89–102. | MR | Zbl

[11] S. M. Lee, R. Tanoto: Three classes of diameter $e$-invariant graphs. Comment. Math. Univ. Carolin. 28 (1987), 227–232. | MR

[12] J. Plesník: Critical graphs of given diameter. Acta Fac. Rer. Nat. Univ. Comenianae, Math. 30 (1975), 71–93. | MR

[13] H. B. Walikar, F. Buckley, K. M. Itagi: Radius-edge-invariant and diameter-edge-invariant graphs. Discrete Math. 272 (2003), 119–126. | DOI | MR

Cité par Sources :