𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On bipartite graphs of diameter 3 and defect 2

✍ Scribed by Charles Delorme; Leif K. Jørgensen; Mirka Miller; Guillermo Pineda-Villavicencio

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
213 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, −2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, −2) ‐graph and bipartite (4, 3, −2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, −2) ‐graphs. The most general of these conditions is that either Δ or Δ−2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, −2)‐graphs, thus establishing that there are no bipartite (Δ, 3, −2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009

📜 SIMILAR VOLUMES

On the spectral radius of bipartite grap
On the spectral radius of bipartite graphs with given diameter
✍ Mingqing Zhai; Ruifang Liu; Jinlong Shu 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 123 KB

Let GB(n, d) be the set of bipartite graphs with order n and diam- eter d. This paper characterizes the extremal graph with the maximal spectral radius in GB(n, d). Furthermore, the maximal spectral radius is a decreasing function on d. At last, bipartite graphs with the second largest spectral radi

On 2-factors of a bipartite graph
On 2-factors of a bipartite graph
✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2-factor with exactly k components? We will prove that if , then, for any bipartite graph H = (U 1 , U 2 ; F ) with |U 1 | ≤ n, |U 2 | ≤ n and ∆(H) ≤ 2, G contains a subgraph i

On diameter of permutation graphs
On diameter of permutation graphs
✍ Gu, Weizhen 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Let G be a connected graph with n vertices. Let a be a permutation in S n . The a-generalized graph over G, denoted by P a (G), consists of two disjoint, identical copies of G along with edges £a(£). In this paper, we investigated the relation between diameter of P a (G) and diameter of G for any pe

2-diameter of de Bruijn graphs
2-diameter of de Bruijn graphs
✍ Li, Qiao; Sotteau, Dominique; Xu, Junming 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 589 KB

This paper shows that in the undirected binary de Bruijn graph of dimension n . UB(n), which has diameter n , there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2-diameter of U B ( n ) is equal to its diameter n .