STRONGLY REGULAR GRAPHS OVER WEAK METRIC SCHEMES AND CHEEGER CONSTANTS OF HAMMING GRAPHS
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Weak metric schemes are a generalized notion of metric schemes. We are interested in the characterization of the strongly regu- lar graphs constructed from weak metric schemes with 2 classes. In this paper we show that the connected strongly regular graphs constructed from the weak metric schemes with 2 classes are complete multipartite graphs, and in fact that the weak metric schemes with 2 classes are equivalent to the complete multipartite graphs. By using our construc- tion, we find the entire list of complete multipartite graphs up to 100 vertices. Additionally, we determine the Cheeger constants of Hamming graphs completely.
Abstract
Weak metric schemes are a generalized notion of metric schemes. We are interested in the characterization of the strongly regu- lar graphs constructed from weak metric schemes with 2 classes. In this paper we show that the connected strongly regular graphs constructed from the weak metric schemes with 2 classes are complete multipartite graphs, and in fact that the weak metric schemes with 2 classes are equivalent to the complete multipartite graphs. By using our construc- tion, we find the entire list of complete multipartite graphs up to 100 vertices. Additionally, we determine the Cheeger constants of Hamming graphs completely.
참고문헌 (12)
- A.E. Brouwer, "Distance Regular Graphs" (1989), Springer-Verlag
- A.E. Brouwer, "Strongly Regular Graphs and Partial Geometries", Enumeration and Design: Papers from the conference on combinatorics, pp.85~122 (1984), Academic Press
- E. Bannai, "Algebraic Combinatorics I, Association Schemes", pp.1984, Ben-jamin
- R. A. Brualdi, "Codes with a poset metric", Discrete Math, 147, pp.57~72 (1995)
- S. Bang, "On generalized semidirect product of association schemes", Discrete Math, 303, pp.5~16 (2005)
- J. Dodziuk, "From Local Times to Global Geometry, control and Physics", pp.68~74 (1986), Pitman
- An algebraic approach to the association schemes of coding theory, "P. Delsarte", ~, pp.Philips Research Reports Supplements, No. 10
- C.D. Godsil, "Association schemes", ~
- 김대산, "Weak metric and weak cometric schemes", 대한수학회지, 46(4), pp.785~812 (2009), 대한수학회
- J.J. Seidel, "Strongly Regular Graphs", Surveys in Combinatorics (Proc. Seventh British Combinatorial Conf), pp.157~180 (1979), Cambridge Uni-versity Press
- J. Tan, "On cheeger inequalities of a graph", Discrete Math, 269, pp.315~323 (2003)
- D.B.West, "Introduction to Graph Theory" (2000), Prentice-Hall