|
|
Prikladnaya Diskretnaya Matematika, 2010, Number 1(7), Pages 105–117
(Mi pdm160)
|
|
|
|
Applied Graph Theory
Minimal edge extensions of some precomplete graphs
M. B. Abrosimov Saratov State University named after N. G. Chernyshevsky, Saratov, Russia
Abstract:
We consider the minimal edge $k$-extensions of precomplete graphs – graphs in which there is a vertex adjacent to all other vertices. The lemma about the marginal value of $k$ when a precomplete graph can have a minimal edge $k$-extension is proved. The full description of all the minimal edge $k$-extensions of precomplete graphs being joins of a complete graph and an empty graph, a chain or a cycle is given.
Keywords:
precomplete graph, minimal edge extension, fault tolerance.
Citation:
M. B. Abrosimov, “Minimal edge extensions of some precomplete graphs”, Prikl. Diskr. Mat., 2010, no. 1(7), 105–117
Linking options:
https://www.mathnet.ru/eng/pdm160 https://www.mathnet.ru/eng/pdm/y2010/i1/p105
|
|