Submatrices of non-tree-realizable distance matrices |
| |
Authors: | JMS Simões-Pereira Christina M Zamfirescu |
| |
Institution: | Department of Computer Science Hunter College USA;Graduate Center of the City University of New York New York New York 10021 USA;Department of Computer Science Hunter College of the City University of New York New York New York 10021 USA |
| |
Abstract: | We deal with distance matrices of real (this means, not necessarily integer) numbers. It is known that a distance matrix D of order n is tree-realizable if and only if all its principal submatrices of order 4 are tree-realizable. We discuss bounds for the number, denoted Qi(D), of non-tree-realizable principal submatrices of order i ? 4 of a non-tree-realizable distance matrix D of order n?i, and we construct some distance matrices which meet extremal conditions on Qi(D). Our starting point is a proof that a non-tree-realizable distance matrix of order 5 has at least two non-tree-realizable principal submatrices of order 4. Optimal realizations (by graphs with circuits) of distance matrices which are not tree-realizable are not yet as well known as optimal realizations which are trees. Using as starting point the optimal realization of the (arbitrary) distance matrix of order 4, we investigate optimal realizations of non-tree-realizable distance matrices with the minimum number of non-tree-realizable principal submatrices of order 4. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |