Constructions of bi-regular cages |
| |
Authors: | G Araujo-Pardo C Balbuena |
| |
Institution: | a Instituto de Matemáticas, Universidad Nacional Autonóma de México, Ciudad Universitaria, México D.F. 04510, Mexico b Departament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Campus Nord, Edifici C2, C/ Jordi Girona 1 i 3, E-08034 Barcelona, Spain c Departamento de Matemáticas, EPS Algeciras, Universidad de Cádiz, Avda Ramón Puyol s/n, E-11202 Algeciras (Cádiz), Spain |
| |
Abstract: | Given three positive integers r,m and g, one interesting question is the following: What is the minimum number of vertices that a graph with prescribed degree set {r,m}, 2≤r<m, and girth g can have? Such a graph is called a bi-regular cage or an ({r,m};g)-cage, and its minimum order is denoted by n({r,m};g). In this paper we provide new upper bounds on n({r,m};g) for some related values of r and m. Moreover, if r−1 is a prime power, we construct the following bi-regular cages: ({r,k(r−1)};g)-cages for g∈{5,7,11} and k≥2 even; and ({r,kr};6)-cages for k≥2 any integer. The latter cages are of order n({r,kr};6)=2(kr2−kr+1). Then this result supports the conjecture that n({r,m};6)=2(rm−m+1) for any r<m, posed by Yuansheng and Liang Y. Yuansheng, W. Liang, The minimum number of vertices with girth 6 and degree set D={r,m}, Discrete Math. 269 (2003) 249-258]. We finalize giving the exact value n({3,3k};8), for k≥2. |
| |
Keywords: | Cage graph Girth |
本文献已被 ScienceDirect 等数据库收录! |
|