| Title:
|
Diameter-invariant graphs (English) |
| Author:
|
Vacek, Ondrej |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
130 |
| Issue:
|
4 |
| Year:
|
2005 |
| Pages:
|
355-370 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
extremal graphs |
| Keyword:
|
diameter of graph |
| Keyword:
|
distance |
| MSC:
|
05C12 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 1112.05033 |
| idMR:
|
MR2182382 |
| DOI:
|
10.21136/MB.2005.134211 |
| . |
| Date available:
|
2009-09-24T22:22:21Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134211 |
| . |
| Reference:
|
[1] V. Bálint, O. Vacek: Radius-invariant graphs.Math. Bohem. 129 (2004), 361–377. MR 2102610 |
| Reference:
|
[2] F. Buckley, F. Harary: Distance in Graphs.Addison-Wesley, Redwood City, 1990. MR 1045632 |
| Reference:
|
[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 1322543 |
| Reference:
|
[4] R. Frucht, F. Harary: On the corona of two graphs.Aequationes Math. 4 (1970), 322–325. MR 0281659, 10.1007/BF01844162 |
| Reference:
|
[5] F. Gliviak: On radially extremal graphs and digraphs, a survey.Math. Bohem. 125 (2000), 215–225. Zbl 0963.05072, MR 1768809 |
| Reference:
|
[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 0265197 |
| Reference:
|
[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 0302503 |
| Reference:
|
[8] N. Graham, F. Harary: Changing and unchanging the diameter of a hypercube.Discrete Appl. Math. 37/38 (1992), 265–274. MR 1176857 |
| Reference:
|
[9] F. Harary: Changing and unchanging invariants for graphs.Bull Malaysian Math. Soc. 5 (1982), 73–78. Zbl 0512.05035, MR 0700121 |
| Reference:
|
[10] S. M. Lee: Design of diameter $e$-invariant networks.Congr. Numerantium 65 (1988), 89–102. Zbl 0800.05011, MR 0992859 |
| Reference:
|
[11] S. M. Lee, R. Tanoto: Three classes of diameter $e$-invariant graphs.Comment. Math. Univ. Carolin. 28 (1987), 227–232. MR 0904748 |
| Reference:
|
[12] J. Plesník: Critical graphs of given diameter.Acta Fac. Rer. Nat. Univ. Comenianae, Math. 30 (1975), 71–93. MR 0398904 |
| Reference:
|
[13] H. B. Walikar, F. Buckley, K. M. Itagi: Radius-edge-invariant and diameter-edge-invariant graphs.Discrete Math. 272 (2003), 119–126. MR 2019205, 10.1016/S0012-365X(03)00189-4 |
| . |
