×

Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel’s conjecture. (English) Zbl 1109.05098

Summary: We analyze Lipták and Tunçel’s conjecture on minimal graphs with \(N_{+}\)-rank \(k\); see L. Lipták and L. Tunçel [Math. Program. B 98, 319–353 (2003; Zbl 1160.90584)]. We present necessary conditions for \(k\)-minimal graphs and describe the family of 2-minimal graphs. We find a 3-minimal graph and show that there is no \(k\)-minimal subdivision of complete graphs for \(k>4\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 1160.90584
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, E.; Cornuéjols, G.; Ceria, S., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 295-324 (1993) · Zbl 0796.90041
[2] Chvátal, V., On certain polytopes associated with graphs, J. Combinat. Theory (B), 18, 138-154 (1975) · Zbl 0277.05139
[3] M. Escalante, M.S. Montelar, G. Nasini, On minimal \(N_+\); M. Escalante, M.S. Montelar, G. Nasini, On minimal \(N_+\) · Zbl 1075.05550
[4] Knuth, D. E., The sandwich theorem, Electron. J. Combinat., 1 (1994) · Zbl 0810.05065
[5] V. Leoni, G. Nasini, On the relationship between disjunctive relaxations and minors in packing and covering problems, preprint, 2003.; V. Leoni, G. Nasini, On the relationship between disjunctive relaxations and minors in packing and covering problems, preprint, 2003. · Zbl 1105.90080
[6] Lipták, L.; Tunçel, L., The stable set problem and the lift-and-project ranks of graphs, Math. Program. B, 98, 319-353 (2003) · Zbl 1160.90584
[7] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190 (1991) · Zbl 0754.90039
[8] G. Nasini, La imperfección de un grafo y su complemento, Anales de las XXX JAIIO-SIO’01, 2001, pp. 102-106.; G. Nasini, La imperfección de un grafo y su complemento, Anales de las XXX JAIIO-SIO’01, 2001, pp. 102-106.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.