×

Row and column orthogonal (0,1)-matrices. (English) Zbl 1148.05045

Summary: We investigate pairs of graphs that can be realized as the row-orthogonal and column-orthogonal graphs of a square \((0,1)\)-matrix, and graphs that can be realized as the row- and column-orthogonal graph of a symmetric \((0,1)\)-matrix. We provide a general construction that shows, in particular, that trees, and all bipartite graphs with a vertex of degree 1 or of diameter at least 9 have such a symmetric realization.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C62 Graph representations (geometric and intersection representations, etc.)
15A54 Matrices over function rings in one or more variables
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0746.05002
[2] Greenberg, H. J.; Lundgren, J. R.; Maybee, J. S., Graph theoretic methods for the qualitative analysis of rectangular matrices, SIAM J. Algebraic Discrete Methods, 2, 227-239 (1981) · Zbl 0498.05047
[3] Monson, S. D.; Pullman, N. J.; Rees, R., A survey of clique and biclique coverings and factorizations of (0,1)-matrices, Bull. ICA, 14, 17-86 (1995) · Zbl 0832.05088
[4] Roberts, F. S.; Tesman, B., Applied Combinatorics (2005), Pearson: Pearson Upper Saddle River, NJ
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.