On minimal N+-rank graphs

ESCALANTE MARIANA SILVINA; MONTELAR MARÍA SUSANA; NASINI GRACIELA LEONOR

Electronic Notes in Discrete Mathematics

ELSEVIER

Lugar: The Netherlands; Año: 2004 vol. 18 p. 109 - 114

1571-0653

Lipták and Tuncel  study the minimum number of nodes needed in a graph to have N+−rank k, proving that it is at least 3k. They conjecture that, for any k, there is a k−minimal graph, i.e. a graph with 3k nodes and N+−rank k. They find one 2−minimal subdivision of K4 and conjecture that there is always a k−minimal subdivision of Kk+2. In this paper, we present some necessary conditions for a graph to be k−minimal. Using these conditions we prove that Lipták and Tuncel’s first conjecture holds for k = 3 showing a 3−minimal graph which is a subdivision of K5. However, from the complete characterization of 2−minimal graphs and the necessary conditions, we prove that the second conjecture is not correct showing a stronger result: for k > 4 there is not a k−minimal subdivision of any complete graph. In order to analyze the existence of k−minimal graphs for k ≥ 4, results on the behavior of ranks under subdivisions in a graph become useful. In this way, in connection with the graph classes B0 and B presented by Lipták and Tuncel, we define a new class B+ that, in particular, contains the known k−minimal graphs. We obtain a characterization of these three classes in terms of the disjunctive rank, allowing us to give a simpler proof of the rank invariance under graph odd subdivisions in these classes.