About graphs critical for the condition for the smallest dimension of orthonormal labeling

Authors

  • Evgenii V. Prosolupov St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;

Abstract

The concept of graph critical for condition that independence number is equal to smallest dimension of orthonormal labeling and strictly less then clique cover number was considered. Necessary and sufficient conditions for graph to be critical in this sense were found. Based on the results sufficient condition for equality of the independence number and the smallest dimension of orthonormal labeling of graph to imply equality of the independence number and the clique cover number was improved. Refs 16. Figs 1.

Keywords:

graph, critical graph, orthonormal labeling, rank, minimal rank, symmetric matrices, clique, independent set, clique cover number, independence number, smallest dimension of orthonormal labeling

Downloads

Download data is not yet available.

Downloads

Published

2015-08-01

How to Cite

Prosolupov, E. V. (2015). About graphs critical for the condition for the smallest dimension of orthonormal labeling. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 2(3), 369–378. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/11171

Issue

Vol. 2 No. 3 (2015)

Section

Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.