Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Lobov A. A., Abrosimov M. B. Vertex extensions of 4-layer graphs and hypercubes. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2022, vol. 22, iss. 4, pp. 536-548. DOI: 10.18500/1816-9791-2022-22-4-536-548, EDN: BHQKFP

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 864)
Article type: 

Vertex extensions of 4-layer graphs and hypercubes

Lobov Alexandr A., Saratov State University
Abrosimov Mikhail Borisovich, Saratov State University

J. P. Hayes proposed a graph-based model of fault tolerant systems, which in a more abstract form corresponds to vertex and edge extensions of graphs. A graph $G^*$ is called a vertex $k$-extension of a graph $G$ if the graph $G$ is embedded in every graph obtained from $G^*$ by removing any $k$ vertices. If no proper part of the graph $G^*$ is a vertex $k$-extension of the graph $G$, then the extension $G^*$ is said to be irreducible. If a vertex $k$-extension has the minimum possible number of vertices and edges, then it is called minimal. The task of finding minimal extensions for an arbitrary graph is computationally difficult. Only for some classes of graphs, it was possible to find a partial or complete description of their minimal vertex extensions. In this paper, we propose a general scheme for constructing vertex 1- and 2-extensions for almost all bipartite graphs, including hypercubes. The hypercube is an interesting graph in terms of its properties and the possibility of using it as a topology of an interconnection network. The minimum vertex extensions for hypercubes are unknown. In practice, trivial 1-extensions are used, which are obtained by adding one vertex and connecting it to all the others. The irreducible 1-extension for the 16-vertex hypercube proposed in this paper contains one less edge than the trivial 1-extension. The article also determines the number of non-isomorphic extensions for each hypercube that can be constructed using the proposed schemes and proves the irreducibility of hypercube vertex 1-extensions.

This work was supported by the Ministry of science and education of the Russian Federation in the framework of the basic part of the scientific research state task (project No. FSRR-2020-0006).
  1. Bogomolov A. M., Salii V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic Foundations of the Theory of Discrete Systems]. Moscow, Fizmatlit, 1997. 368 p. (in Russian). EDN: XYCVTZ
  2. Abrosimov M. B. Grafovye modeli otkazoustojchivosti [Graph Models of Fault Tolerance]. Saratov, Saratov University Publ., 2012. 192 p. (in Russian). EDN: QMXQLB
  3. Hayes J. P. A graph model for fault-tolerant computing systems. IEEE Transactions on Computers, 1976, vol. C-25, no. 9, pp. 875–884. https://doi.org/10.1109/TC.1976.1674712
  4. Harary F., Hayes J. P. Edge fault tolerance in graphs. Networks, 1993, vol. 23, iss. 2, pp. 135–142. https://doi.org/10.1002/net.3230230207
  5. Harary F., Hayes J. P. Node fault tolerance in graphs. Networks, 1996, vol. 27, iss. 1, pp. 19–23. https://doi.org/10.1002/(SICI)1097-0037(199601)27:1<19::AID-NET2>3.0.CO;2-H
  6. Abrosimov M. B. On the complexity of some problems related to graph extensions. Mathematical Notes, 2010, vol. 88, iss. 5–6, pp. 619–625. https://doi.org/10.1134/S0001434610110015, EDN: OHNTMT
  7. Abrosimov M. B., Kamil I. A. K., Lobov A. A. Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2019, vol. 19, iss. 4, pp. 479–486 (in Russian). https://doi.org/10.18500/1816-9791-2019-19-4-479-486, EDN: YXOMDX
  8. Abrosimov M. B., Sudani H. H. K., Lobov A. A. Construction of all minimal edge extensions of the graph with isomorphism rejection. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2020, vol. 20, iss. 1, pp. 105–115 (in Russian).https://doi.org/10.18500/1816-9791-2020-20-1-105-115, EDN: PXDRGJ
  9. Harary F., Hayes J. P., Wu H.-J. A survey of the theory of hypercube graphs. Computers & Mathematics with Applications, 1988, vol. 15, iss. 4, pp. 277–289. https://doi.org/10.1016/0898-1221(88)90213-1
  10. Biggs N. Distance-transitive graphs. In: Algebraic Graph Theory. Cambridge, Cambridge University Press, 1974, pp. 155–163. https://doi.org/10.1017/CBO9780511608704.021