The Structure of Trivalent Graphs with Minimal Eigenvalue Gap
Barry Guiduli
DOI: 10.1023/A:1008669009563
Abstract
Let G be a connected trivalent graph on nvertices ( n 
10) such that among all connected trivalentgraphs on n vertices, G has the largest possiblesecond eigenvalue. We show that G must be reduced path-like, i.e. G must be of the form: where theends are one of the following:(the right-hand end block is the mirror image of one of the blocks shown)and the middle blocks are one of the following: This partially solves a conjecture implicit in a paper of Bussemaker, 
obelji 
, Cvetkovi , and Seidel [3].
10) such that among all connected trivalentgraphs on n vertices, G has the largest possiblesecond eigenvalue. We show that G must be reduced path-like, i.e. G must be of the form: where theends are one of the following:(the right-hand end block is the mirror image of one of the blocks shown)and the middle blocks are one of the following: This partially solves a conjecture implicit in a paper of Bussemaker, obelji , Cvetkovi , and Seidel [3].Pages: 321–329
Keywords: trivalent graph; eigenvalue
Full Text: PDF
References
1. N. Alon, “Eigenvalues and expanders,” Combinatorica 6 (1986), pp. 83-96.
2. N. Alon and V. D. Milman, “Eigenvalues, expanders, and superconcentrators,” Proc. 25th IEEE FOCS, (Singer Island, Florida, 1984), pp. 320-322.
3. F. C. Bussemaker, S. \check Cobeljić, D. M. Cvetković, and J. J. Seidel, Computer investigation of cubic graphs. Technological University Eindhoven, 1976. (Report 76-WSK-01).
4. F. C. Bussemaker, S. \check Cobeljić, D. M. Cvetković, and J. J. Seidel, “Cubic graphs on \leq 14 vertices,” J. Combin. Theory, Ser. B 23 (1977), pp. 234-235.
5. M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J. 23 (1973), pp. 298-305.
6. C. Brand, B. Guiduli, and W. Imrich, “The characterization of trivalent graphs with minimal eigenvalue gap,” preprint, 1996.
2. N. Alon and V. D. Milman, “Eigenvalues, expanders, and superconcentrators,” Proc. 25th IEEE FOCS, (Singer Island, Florida, 1984), pp. 320-322.
3. F. C. Bussemaker, S. \check Cobeljić, D. M. Cvetković, and J. J. Seidel, Computer investigation of cubic graphs. Technological University Eindhoven, 1976. (Report 76-WSK-01).
4. F. C. Bussemaker, S. \check Cobeljić, D. M. Cvetković, and J. J. Seidel, “Cubic graphs on \leq 14 vertices,” J. Combin. Theory, Ser. B 23 (1977), pp. 234-235.
5. M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J. 23 (1973), pp. 298-305.
6. C. Brand, B. Guiduli, and W. Imrich, “The characterization of trivalent graphs with minimal eigenvalue gap,” preprint, 1996.