Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
On graphs containing a given graph as median
Authors: A. Poshtaru, R. Boliac
– 0.15 Mb
Abstract
P.J. Slater demonstrated that any connected graph G is the median of a graph G* and indicated the construction of G*. His construction requires O(n2) new vertices, where n is the number of G vertices of G. In this paper the same problem is considered and some new constructions of G* are presented. The number of new vertices added to G is considerably improved. From our constructions it follows that in the general case n new vertices are necessary.A. Poshtaru,
Republic of Moldova's State University,
Department of Mathematics and Cybernetics,
A.Mateevici str., 60,
Kishinev, 277003, Moldova
R.Boliac,
Institute of Mathematics,
Academy of Sciences of Moldova,
5 Academiei str.,
Kishinev, 277028, Moldova.
e-mail:
Republic of Moldova's State University,
Department of Mathematics and Cybernetics,
A.Mateevici str., 60,
Kishinev, 277003, Moldova
R.Boliac,
Institute of Mathematics,
Academy of Sciences of Moldova,
5 Academiei str.,
Kishinev, 277028, Moldova.
e-mail:
Fulltext
– 0.15 Mb
Contents
- The structural robustness of multiprocessor computing system
- On the Family of Conditional Embedded Implicational Dependencies
- Fast software encryption system based on local pseudorandomness
- Quasi-Newton Methods for Solving Nonlinear Programming Problems
- On graphs containing a given graph as median
- Numerical implementation of mechanical quadratures method for solving singular integral equations given on closed smooth contours
- The aproximation of functions in generalized Holder spaces
- Macroeconomic model of national economy development
