|
Applied Theory of Coding, Automata and Graphs
Upper and lower bounds of the number of additional arcs in a minimal edge $1$-extension of oriented path
M. B. Abrosimova, O. V. Modenovab a Saratov State University, Saratov
b Saratov
Abstract:
The following upper and lower bounds of the number of additional arcs $ec(P_n)$ in a minimal edge $1$-extension of an oriented path $P_n$ are obtained: 1) for $P_n$ which has ends of different types and is not isomorphic to Hamiltonian path or to orientation consisting of alternating sources and sinks, $\lceil n/6\rceil+1\leq ec(P_n)\leq n+1$; 2) for $P_n$ with ends of equal types, $\lceil n/4\rceil+1\leq ec(P_n)\leq n+1$.
Keywords:
minimal edge extension, path orientation, fault-tolerance.
Citation:
M. B. Abrosimov, O. V. Modenova, “Upper and lower bounds of the number of additional arcs in a minimal edge $1$-extension of oriented path”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 134–136
Linking options:
https://www.mathnet.ru/eng/pdma347 https://www.mathnet.ru/eng/pdma/y2017/i10/p134
|
Statistics & downloads: |
Abstract page: | 100 | Full-text PDF : | 24 | References: | 29 |
|