Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya, 2014, Issue 1, Pages 90–103 (Mi vspui173)  

Applied mathematics

On sufficient conditions for equality of the independence number and the clique cover number for a class of graphs

E. V. Prosolupov

St. Petersburg State University, 199034, St. Petersburg, Russian Federation
References:
Abstract: For a simple graph sufficient condition are improved to ensure that equality of the independence number and the smallest dimension of orthonormal labeling of graph result in equality of the independence number and the clique cover number. To formulate that condition a class of graphs with certain structure is described. Let $W$ be a wheel-graph with odd number of vertices $n\geq 5$. Then delete every second edge from center vertex of the graph. This results in obtaining a structure of sequence of chordless cycles $C_4$ with a common vertex and common edges in pairs. Some properties of such a structure are examined. It is proved that every graph $H$ with property $\alpha(H) = d(H) < \overline\chi(H)$ is characterized by this structure. So, if for some graph $G$ independence number is equal to smallest dimension of orthonormal labeling of $G$ and the graph $G$ is free of the described structure, then independence number of $G$ is equal to clique cover number of $G$. It discusses how the conditions have been improved in comparison with previously known conditions. Bibliogr. 17. Il. 10.
Keywords: graph, orthonormal labeling, rank, minimal rank, symmetric matrices, clique, independent set, clique cover number, independence number, smallest dimension of orthonormal labeling.
Received: October 31, 2013
Document Type: Article
UDC: 519.17
Language: Russian
Citation: E. V. Prosolupov, “On sufficient conditions for equality of the independence number and the clique cover number for a class of graphs”, Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 2014, no. 1, 90–103
Citation in format AMSBIB
\Bibitem{Pro14}
\by E.~V.~Prosolupov
\paper On sufficient conditions for equality of the independence number and the clique cover number for a class of graphs
\jour Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.
\yr 2014
\issue 1
\pages 90--103
\mathnet{http://mi.mathnet.ru/vspui173}
Linking options:
  • https://www.mathnet.ru/eng/vspui173
  • https://www.mathnet.ru/eng/vspui/y2014/i1/p90
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025