On a Conjecture on a Laplacian Matrix with Distinct Integral Spectrum12. Issue 2 (28th August 2012)

• Record Type: Journal Article
• Authors: Goldberger, Assaf; Neumann, Michael
• Is Part Of: Journal of graph theory. Volume 72:Issue 2(2013)
• Page Start: 178
• Page End: 208
• Publication Date: 2012-08-28
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21638
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>In a paper Fallat et al. (J Graph Theory 50 (2005), 162–174) consider the question of the existence of simple graphs <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788j3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">G</mml:mi></mml:math> on <italic>n</italic> vertices whose Laplacian matrix <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788kn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>L</mml:mi><mml:mo>(</mml:mo><mml:mi mathvariant="script">G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> has an integral spectrum consisting of simple eigenvalues only in the range <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788dw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mo>...</mml:mo><mml:mo>, </mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math>, 0 always being, automatically, one of the eigenvalues. They completely characterize the case when <italic>n</italic> is one of the eigenvalues, but for the case when <italic>n</italic> is not, they conjecture that there are no such graphs. In that paper it is shown that, indeed, there are no such graphs for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788ff" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≤</mml:mo><mml:mn>11</mml:mn></mml:mrow></mml:math>. In this paper we show that the conjecture is true for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788g0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>6</mml:mn><mml:mo>, </mml:mo><mml:mn>649</mml:mn><mml:mo>, </mml:mo><mml:mn>688</mml:mn><mml:mo>, </mml:mo><mml:mn>933</mml:mn><mml:mo>.</mml:mo></mml:mrow></mml:math> We actually consider the nonexistence of graphs whose Laplacians are realized by more general spectra <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788hj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mi>λ</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:mo>⋯</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mi>λ</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math>, with <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788bs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math>, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq78897" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>≤</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math>, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq788cb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math>, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq78874" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math>, and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1tq7888p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21638:equation:jgt21638-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math>, subject to certain trace conditions. We show that, indeed, for sufficiently large <italic>n</italic> such graphs do not exist. Our methods are both graph theoretical and algebraic. In certain cases we refine the Cauchy interlacing theorem. Finally, rather than work with Laplacians which have nonpositive off‐Diagonal entries, we transform the problems to the realizability of spectra of nonnegative matrices which we term <italic>anti‐Laplacians</italic>.</p> </abstract>