|
Prikladnaya Diskretnaya Matematika. Supplement, 2013, Issue 6, Pages 71–72
(Mi pdma105)
|
|
|
|
Applied graph theory
About the lower bounds for the number of additional arcs in a minimal vertex 1-extension of oriented path
M. B. Abrosimov, O. V. Modenova Saratov State University
Abstract:
A graph $G^*$ with $n + k$ vertices is vertex $k$-extension of a graph $G$ if every graph obtained by removing any $k$ vertices from $G^*$ contains $G$; it is called minimal vertex $k$-extension of $G$ if it has the least number of arcs among all vertex $k$-extensions of graph $G$ with $n+k$ vertices. A lower bound for the number of additional arcs in minimal vertex 1-extension of an oriented path is given.
Keywords:
graph, minimal vertex extension, fault tolerance.
Citation:
M. B. Abrosimov, O. V. Modenova, “About the lower bounds for the number of additional arcs in a minimal vertex 1-extension of oriented path”, Prikl. Diskr. Mat. Suppl., 2013, no. 6, 71–72
Linking options:
https://www.mathnet.ru/eng/pdma105 https://www.mathnet.ru/eng/pdma/y2013/i6/p71
|
Statistics & downloads: |
Abstract page: | 154 | Full-text PDF : | 58 | References: | 29 |
|