DSpace DSpace Softwareについて 愛知教育大学

DSpace at 愛知教育大学 >
02 学術雑誌論文(学外発行分) >
022 外国雑誌 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10424/6862

タイトル: Linear programming bounds for regular graphs
著者: Nozaki, Hiroshi
著者(訳): 野崎, 寛
出典: Graphs and combinatorics. 2015, 31(6), p. 1973-1984.
出版者: Springer
抄録: Delsarte, Goethals, and Seidel (1977) used the linear programming method in order to find bounds for the size of spherical codes endowed with prescribed inner products between distinct points in the code. In this paper, we develop the linear programming method to obtain bounds for the number of vertices of connected regular graphs endowed with given distinct eigenvalues. This method is proved by some "dual" technique of the spherical case, motivated from the theory of association scheme. As an application of this bound, we prove that a connected k-regular graph satisfying g > 2d − 1 has the minimum second-largest eigenvalue of all k-regular graphs of the same size, where d is the number of distinct non-trivial eigenvalues, and g is the girth. The known graphs satisfying g > 2d − 1 are Moore graphs, incidence graphs of regular generalized polygons of order (s, s), triangle-free strongly regular graphs, and the odd graph of degree 4.
URI: http://hdl.handle.net/10424/6862
言語: en
NII資源タイプ: Journal Article
DOI: info:doi/10.1007/s00373-015-1613-7
権利情報: Copyright: Springer Japan 2015
The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-015-1613-7.
著者版フラグ: author
出現コレクション:022 外国雑誌


ファイル 記述 サイズフォーマット
nozakih001.pdf106.95 kBAdobe PDF見る/開く



DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - ご意見をお寄せください