Bipartite biregular Moore graphs
| Autor: | Nacho López, Cristina Dalfó, Miguel Angel Fiol, Gabriela Araujo-Pardo |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
| Rok vydání: | 2021 |
| Předmět: |
Moore bound
0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Diameter Computer Science::Discrete Mathematics FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Mathematics - Combinatorics Bipartite biregular graphs Mathematics Discrete mathematics Mathematics::Combinatorics Degree (graph theory) Grafs Teoria de 020206 networking & telecommunications Graph theory 010201 computation theory & mathematics Independent set Bipartite graph Combinatorics (math.CO) Isomorphism 05 Combinatorics::05C Graph theory [Classificació AMS] Adjacency spectrum Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] 5C35 51E12 05C50 |
| Zdroj: | Repositorio Abierto de la UdL Universitad de Lleida UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Discrete Mathematics |
| Popis: | A bipartite graph $G=(V,E)$ with $V=V_1\cup V_2$ is biregular if all the vertices of a stable set $V_i$ have the same degree $r_i$ for $i=1,2$. In this paper, we give an improved new Moore bound for an infinite family of such graphs with odd diameter. This problem was introduced in 1983 by Yebra, Fiol, and F\`abrega.\\ Besides, we propose some constructions of bipartite biregular graphs with diameter $d$ and large number of vertices $N(r_1,r_2;d)$, together with their spectra. In some cases of diameters $d=3$, $4$, and $5$, the new graphs attaining the Moore bound are unique up to isomorphism. Comment: 19 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|