Diameter-invariant graphs

Ondrej Vacek

Mathematica Bohemica (2005)

  • Volume: 130, Issue: 4, page 355-370
  • ISSN: 0862-7959

Abstract

top
The diameter of a graph is the maximal distance between two vertices of . A graph is said to be diameter-edge-invariant, if for all its edges, diameter-vertex-invariant, if for all its vertices and diameter-adding-invariant if for all edges of the complement of the edge set of . This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.

How to cite

top

Vacek, Ondrej. "Diameter-invariant graphs." Mathematica Bohemica 130.4 (2005): 355-370. <http://eudml.org/doc/249594>.

@article{Vacek2005,
abstract = {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.},
author = {Vacek, Ondrej},
journal = {Mathematica Bohemica},
keywords = {extremal graphs; diameter of graph; distance; extremal graph; diameter of graph; distance},
language = {eng},
number = {4},
pages = {355-370},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Diameter-invariant graphs},
url = {http://eudml.org/doc/249594},
volume = {130},
year = {2005},
}

TY - JOUR
AU - Vacek, Ondrej
TI - Diameter-invariant graphs
JO - Mathematica Bohemica
PY - 2005
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 130
IS - 4
SP - 355
EP - 370
AB - 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.
LA - eng
KW - extremal graphs; diameter of graph; distance; extremal graph; diameter of graph; distance
UR - http://eudml.org/doc/249594
ER -

References

top
  1. Radius-invariant graphs, Math. Bohem. 129 (2004), 361–377. (2004) MR2102610
  2. Distance in Graphs, Addison-Wesley, Redwood City, 1990. (1990) MR1045632
  3. Changing and unchanging of the radius of graph, Linear Algebra Appl. 217 (1995), 67–82. (1995) MR1322543
  4. 10.1007/BF01844162, Aequationes Math. 4 (1970), 322–325. (1970) MR0281659DOI10.1007/BF01844162
  5. On radially extremal graphs and digraphs, a survey, Math. Bohem. 125 (2000), 215–225. (2000) Zbl0963.05072MR1768809
  6. On certain classes of graphs of diameter two without superfluous edges, Acta Fac. Rer. Nat. Univ. Comenianae, Math. 21 (1968), 39–48. (1968) MR0265197
  7. On the extension of graphs with a given diameter without superfluous edges, Mat. Cas. Slovensk. Akad. Vied 19 (1969), 92–101. (1969) MR0302503
  8. Changing and unchanging the diameter of a hypercube, Discrete Appl. Math. 37/38 (1992), 265–274. (1992) MR1176857
  9. Changing and unchanging invariants for graphs, Bull Malaysian Math. Soc. 5 (1982), 73–78. (1982) Zbl0512.05035MR0700121
  10. Design of diameter -invariant networks, Congr. Numerantium 65 (1988), 89–102. (1988) Zbl0800.05011MR0992859
  11. Three classes of diameter -invariant graphs, Comment. Math. Univ. Carolin. 28 (1987), 227–232. (1987) MR0904748
  12. Critical graphs of given diameter, Acta Fac. Rer. Nat. Univ. Comenianae, Math. 30 (1975), 71–93. (1975) MR0398904
  13. 10.1016/S0012-365X(03)00189-4, Discrete Math. 272 (2003), 119–126. (2003) MR2019205DOI10.1016/S0012-365X(03)00189-4

NotesEmbed ?

top

You must be logged in to post comments.