×

0-1 matrices with zero trace whose squares are 0-1 matrices. (English) Zbl 1410.15058

Summary: In this paper, we determine the maximum number of nonzero entries in 0-1 matrices of order \(n\) with zero trace whose squares are 0-1 matrices when \(n \geq 8\). The extremal matrices attaining this maximum number are also characterized.

MSC:

15B36 Matrices of integers
05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bollobás, B., Extremal Graph Theory, Handbook of Combinatorics, vols. 1, 2, 1231-1292 (1995), Elsevier Sci. B. V.: Elsevier Sci. B. V. Amsterdam · Zbl 0844.05054
[2] Brown, W. G.; Harary, F., Extremal digraphs, (Combinatorial Theory and Its Applications, I. Combinatorial Theory and Its Applications, I, Proc. Colloq., Balatonfüred, 1969 (1970), North-Holland: North-Holland Amsterdam), 135-198 · Zbl 0209.28501
[3] Brown, W. G.; Simonovits, M., Extremal multigraph and digraph problems, (Paul Erdős and His Mathematics, II. Paul Erdős and His Mathematics, II, Budapest, 1999. Paul Erdős and His Mathematics, II. Paul Erdős and His Mathematics, II, Budapest, 1999, Bolyai Soc. Math. Stud., vol. 11 (2002), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 157-203 · Zbl 1029.05080
[4] Huang, Z.; Lyu, Z., Extremal digraphs avoiding an orientation of \(C_4\) · Zbl 1435.05093
[5] Huang, Z.; Lyu, Z.; Qiao, P., Turán problems for digraphs avoiding different walks of a given length with the same endpoints · Zbl 1414.05133
[6] Huang, Z.; Zhan, X., Digraphs that have at most one walk of a given length with the same endpoints, Discrete Math., 311, 70-79 (2011) · Zbl 1225.05115
[7] Simonovits, M., A method for solving extremal problems in graph theory, stability problems, (Theory of Graphs. Theory of Graphs, Proc. Colloq., Tihany, 1966 (1968), Academic Press: Academic Press New York), 279-319 · Zbl 0164.24604
[8] Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48, 436-452 (1941), (Hungarian) · JFM 67.0732.03
[9] Turán, P., On the theory of graphs, Colloq. Math., 3, 19-30 (1954) · Zbl 0055.17004
[10] Wu, H., On the 0-1 matrices whose squares are 0-1 matrices, Linear Algebra Appl., 432, 2909-2924 (2010) · Zbl 1195.05016
[11] Zhan, X., Matrix Theory, Graduate Studies in Mathematics, vol. 147 (2013), American Mathematical Society: American Mathematical Society Providence, RI
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.