Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On New Record Graphs Close to Bipartite Moore Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

The modelling of interconnection networks by graphs motivated the study of several extremal problems that involve well known parameters of a graph (degree, diameter, girth and order) and optimising one of the parameters given restrictions on some of the others. Here we focus on bipartite Moore graphs, that is, bipartite graphs attaining the optimum order, fixed either the degree/diameter or degree/girth. The fact that there are very few bipartite Moore graphs suggests the relaxation of some of the constraints implied by the bipartite Moore bound. First we deal with local bipartite Moore graphs. We find in some cases those local bipartite Moore graphs with local girths as close as possible to the local girths given by a bipartite Moore graph. Second, we construct a family of \((q+2)\)-bipartite graphs of order \(2(q^2+q+5)\) and diameter 3, for q a power of prime. These graphs attain the record value for \(q=9\) and improve the values for \(q=11\) and \(q=13\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Abajo, E., Araujo-Pardo, G., Balbuena, C., Bendala, M.: New families of small regular graphs of girth 5. Discret. Math. 340(8), 1878–1888 (2017)

    Article  Google Scholar 

  2. Abreu, M., Araujo-Pardo, G., Balbuena, C., Labbate, D.: Families of small regular graphs of girth 5. Discret. Math. 312, 2832–2842 (2012)

    Article  MathSciNet  Google Scholar 

  3. Araujo-Pardo, G., de la Cruz, C., González-Moreno, D.: Mixed Cages: monotony, connectivity and upper bounds. In review. arXiv:2009.13709

  4. J.C. Bermont C. Delorme, Farhi, G.: Large graphs with given degree and diameter. III., Graph theory (Cambridge, 1981), North-Holland Math. Stud., 62, North-Holland, Amsterdam-New York, pp 23–31 (1982)

  5. Capdevila, C., Conde, J., Exoo, G., Gimbert, J., López, N.: Ranking measures for radially Moore graphs. Networks 56(4), 255–262 (2010)

    Article  MathSciNet  Google Scholar 

  6. Dalfó, C., Fiol, M.A., López, N.: On bipartite-mixed graphs. J. Graph Theory 89(4), 386–394 (2018)

    Article  MathSciNet  Google Scholar 

  7. Delorme, C., Farhi, G.: Large graphs with given degree and diameter. I. IEEE Trans. Comput. 33(9), 857–860 (1984)

    Article  MathSciNet  Google Scholar 

  8. Exoo, G., Gimbert, J., López, N., Gómez, J.: Radial Moore graphs of radius three. Discret. Appl. Math. 160(10), 1507–1512 (2012)

    Article  MathSciNet  Google Scholar 

  9. Exoo, G., Jajcay, R.: Dynamic cage survey. Electron. J. Combinat. 16. #DS16v3 (2016)

  10. Feira-Purón, R., Miller, M., Pineda-Villavicencio, G.: On large bipartite graphs of diameter 3. Discret. Math. 4, 381–390 (2013)

    Article  MathSciNet  Google Scholar 

  11. Hafner, P.R.: Geometric realisation of the graphs of McKay–Miller–Sirán. J. Comb. Theory Ser. B 90, 223–232 (2004)

    Article  Google Scholar 

  12. Lee, G.: Abstract algebra. Springer, Berlin (2018)

    Book  Google Scholar 

  13. Gómez, J., Miller, M.: On the existence of radial Moore graphs for every radius and every degree. Eur. J. Combin. 47, 15–22 (2015)

    Article  MathSciNet  Google Scholar 

  14. McKay, B.D.: Nauty User’s Guide. Technical Report TR-CS-90-02, Computer Science Department, Australian National University (1990)

  15. Miller, M., Širáň, J.: Moore graphs and beyond: a survey. Electron. J. Combin. 20 2. #DS14v3, (2016)

  16. Tang, J., Miller, M., Lin, Y.: HSAGA and its application for the construction of near-Moore digraphs. J. Discret. Algorithms 6(1), 73–84 (2008)

    Article  MathSciNet  Google Scholar 

  17. The degree-diameter problem for graphs: https://combgraph.upc.edu/en/resources

  18. CombinatoricsWiki: http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Bipartite_Graphs

Download references

Acknowledgements

G. Araujo would like to thank Rubén Alfaro for his help and computation assistance at the first of the construction on the graph given in Sect. 3. The authors wish to thank the anonymous referees for their valuable suggestions and remarks that contribute to improving the paper.

Funding

Research of N. López was supported in part by the MCIN/AEI/10.13039/501100011033 through Grant PID2020-115442RB-I00 (Spanish Ministerio de Ciencia e Innovacion) and research of G. Araujo was supported by PASPA-DGAPA and CONACyT Sabbatical Stay 2020, CONACyT-México under Project 282280, 47510664 and PAPIIT-México under Projects IN107218, IN108121.

Author information

Authors and Affiliations

  1. Instituto de Matemáticas, Universidad Nacional Autonóma de México, 04510, Mexico, Mexico D.F., Mexico

    Gabriela Araujo

  2. Departament de Matemàtica, Universitat de Lleida, Jaume II 69, 25001, Lleida, Spain

    Nacho López

Authors
  1. Gabriela Araujo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nacho López
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gabriela Araujo.

Ethics declarations

Conflict of interest

The authors have not disclosed any competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Araujo, G., López, N. On New Record Graphs Close to Bipartite Moore Graphs. Graphs and Combinatorics 38, 110 (2022). https://doi.org/10.1007/s00373-022-02500-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-022-02500-3

Keywords

Search

Navigation