Title:
|
Constructions of small regular bipartite graphs of girth 6
|
Author:
|
Araujo Pardo, M. Gabriela; Balbuena Martínez, Maria Camino Teófila
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
Abstract:
|
In this article, some structures in the projective plane of order q are found which allow us to construct small k - regular balanced bipartite graphs of girth 6 for all k ≤ q.
When k = q, the order of these q-regular graphs is 2(q^2−1); and when k ≤ q−1, the order of these k -regular graphs is 2(qk − 2). Moreover, the incidence matrix of
a k -regular balanced bipartite graph of girth 6 having 2(qk −2) vertices, where k is an integer and q is a prime power with 3 ≤ k ≤ q − 1, is provided. These graphs improve upon the best known upper bounds for the number of vertices in regular graphs of girth 6. |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Magic squares -Projective planes -Bipartite graphs -Grafs, Teoria de -Geometria projectiva -Quadrats màgics |
Rights:
|
|
Document type:
|
Article - Published version Article |
Share:
|
|