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

E. V. Prosolupov

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2014), pp. 90-103

Résumé

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.

Détail

Keywords: graph, orthonormal labeling, rank, minimal rank, symmetric matrices, independent set, clique cover number, independence number, smallest dimension of orthonormal labeling.
Mots-clés : clique

Bibliographie

[1] Barioli F., Barrett W., Butler S., Cioabă S. M., Cvetković D., Fallat S. M., Godsil C., Haemers W., Hogben L., Mikkelson R., Narayan S., Pryporova O., Sciriha I., So W., Stevanović D., van der Holst H., Meulen K. V., Wehe A. W., “Zero forcing sets and the minimum rank of graphs”, Linear Algebra Appl., 428 (2008), 1628–1648 | DOI | MR | Zbl

[2] Berman A., Friedland S., Hogben L., Rothblum U. G., Shader B., “Minimum Rank of Matrices Described by a Graph or Pattern over the Rational, Real and Complex Numbers”, Electron. J. Combinat., 15 (2008), R25, 19 pp. | MR | Zbl

[3] Liang-Hao Huang, Gerard J. Chang, Hong-Gwa Yeh, “On minimum rank and zero forcing sets of a graph”, Linear Algebra Appl., 432 (2010), 2961–2973 | DOI | MR | Zbl

[4] Liang-Hao Huang, Gerard J. Chang, Hong-Gwa Yeh, “A note on universally optimal matrices and field independence of the minimum rank of a graph”, Linear Algebra Appl., 433 (2010), 585–594 | DOI | MR | Zbl

[5] Fallat S. M., Hogben L., “The minimum rank of symmetric matrices described by a graph: a survey”, Linear Algebra Appl., 426 (2007), 558–582 | DOI | MR | Zbl

[6] Hogben L., “Minimum rank problems”, Linear Algebra Appl., 432 (2010), 1961–1974 | DOI | MR | Zbl

[7] Webpage for the 2006 American Institute of Mathematics workshop http://aimath.org/pastworkshops/matrixspectrum.html

[8] Briët J., Buhrman H., Gijswijt D., “Violating the Shannon capacity of metric graphs with entanglement”, Proc. of the National Academy of Sciences of the United States of America, 2012 | DOI

[9] Dobrynin V. Ju., “On graph classification based on a minimum rank of a matrix associated with a graph”, Vestnik S.-Peterb. un-ta, ser. 10: Prikladnaya matematika, informatika, processy upravleniya, 2004, no. 3, 30–38 | Zbl

[10] Lovász L., “On the Shannon capacity of graphs”, IEEE Trans. Inform. Theory, 25 (1979), 1–7 | DOI | MR | Zbl

[11] Jethava V., Martinsson A., Bhattacharyya C., Dubhashi D. P., “The Lovasz $\vartheta$ function, SVMs and finding large dense subgraphs”, Advances in Neural Information Processing Systems, 25 (2012), 1169–1177

[12] Duan R., Severini S., Winter A., “Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number”, IEEE Trans. Inform. Theory, 59 (2013), 1164–1174 | DOI | MR

[13] Goemans M. X., “Semidefinite programming in combinatorial optimization”, Math. Program., 79 (1997), 143–161 | MR | Zbl

[14] Dobrynin V. Yu., “On the function “sandwiched” between $\alpha(G)$ and $\overline\chi(G)$”, Electron. J. Combinat., 4 (1997), R19, 3 pp. | MR | Zbl

[15] Dobrynin V., Pliskin M., Prosolupov E., “On the functions with values from $[\alpha(G),\overline\chi(G)]$”, Electron. J. Combinat., 11:5 (2004), 5 | MR | Zbl

[16] Prosolupov E. V., “About the gap between the minimal dimension of the orthonormal labeling and size of smallest clique covering of a graph”, Vestnik S.-Peterb. un-ta, ser. 1: Matematica, mexanica, astronomia, 2004, no. 4, 51–57 | MR | Zbl

[17] Dobrynin V., “On the rank of a matirx associated with graph”, Discrete Mathematics, 276:1–3 (2004), 169–175 | DOI | MR | Zbl