On large bipartite graphs of diameter 3

DOI10.1016/J.DISC.2012.11.013MaRDI QIDQ1937548zbMATH OpenOpenAlexFDO

Authors Ramiro Feria-Purón, Mirka Miller, Guillermo Pineda-Villavicencio

Publication date 1 March 2013

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.3588

zbMATH Keywords

bipartite Moore bounddefectdegree/diameter problem for bipartite graphslarge bipartite graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We consider the bipartite version of the {it degree/diameter problem}, namely, given natural numbers $dge2$ and $Dge2$, find the maximum number $N^b(d,D)$ of vertices in a bipartite graph of maximum degree $d$ and diameter $D$. In this context, the bipartite Moore bound $M^b(d,D)$ represents a general upper bound for $N^b(d,D)$. Bipartite graphs of order $M^b(d,D)$ are very rare, and determining $N^b(d,D)$ still remains an open problem for most $(d,D)$ pairs. This paper is a follow-up to our earlier paper cite{FPV12}, where a study on bipartite $(d,D,-4)$-graphs (that is, bipartite graphs of order $M^b(d,D)-4$) was carried out. Here we first present some structural properties of bipartite $(d,3,-4)$-graphs, and later prove there are no bipartite $(7,3,-4)$-graphs. This result implies that the known bipartite $(7,3,-6)$-graph is optimal, and therefore $N^b(7,3)=80$. Our approach also bears a proof of the uniqueness of the known bipartite $(5,3,-4)$-graph, and the non-existence of bipartite $(6,3,-4)$-graphs. In addition, we discover three new largest known bipartite (and also vertex-transitive) graphs of degree 11, diameter 3 and order 190, result which improves by 4 vertices the previous lower bound for $N^b(11,3)$.

Recommendations

• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• On bipartite graphs of diameter 3 and defect 2
• scientific article; zbMATH DE number 4059445
• Large bipartite Cayley graphs of given degree and diameter
• Diameter three orientability of bipartite graphs
• Large (d,D, D',s)-bipartite digraphs
• New class of integral bipartite graphs with large diameter
• Large sets of \(K_{3,3}\)-decomposition of complete bipartite graphs
• Bipartite graphs of large clique-width
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three

Cited in

(8)

• On new record graphs close to bipartite Moore graphs
• The degree/diameter problem for mixed abelian Cayley graphs
• scientific article; zbMATH DE number 5545497 (Why is no real title available?)
• scientific article; zbMATH DE number 4059445 (Why is no real title available?)
• Bipartite regular graphs with fixed diameter
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• Large bipartite Cayley graphs of given degree and diameter
• Bipartite diametrical graphs of diameter 4 and extreme orders

This page was built for publication: On large bipartite graphs of diameter 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1937548)