✦ LIBER ✦

A remark on Mulder's conjecture about interval-regular graphs

✍ Scribed by K. Nomura

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 184 KB
Volume: 147
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00178-l

No coin nor oath required. For personal study only.

✦ Synopsis

Let F be a connected graph. F is said to be interval-regular if I F~_ l(u) uF(x )J =. i holds for all vertices u and x ~ Fi(u), i > 0. For u, v e F, let I (u, v) denote the set of all vertices on a shortest path connecting u, v. A subset W of V(F) is said to be convex if l(u,v) c W holds for each u, v~ W.

In (Mulder, 1982) Mulder conjectured that every interval 1(u, v) in a interval-regular graph is convex. In this paper, we consider this problem for distance-regular graphs. We shall prove that, in a distance-regular interval-regular graph having a triangle, l(u, v) is convex for every vertices u, v at distance 3.

📜 SIMILAR VOLUMES

On Kotzig's conjecture for graphs with a

On Kotzig's conjecture for graphs with a regular path-connectedness

✍ Keyi Xing; Baosheng H.U 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 397 KB

Kotzig (see Bondy and Murty (1976)) conjectured that there exists no graph with the property that every pair of vertices is connected by a unique path of length k, k>2. Here we prove this conjecture for k> 12.

On a Conjecture about Trees in Graphs wi

On a Conjecture about Trees in Graphs with Large Girth

✍ Tao Jiang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 169 KB

The girth of a graph G is the length of a shortest cycle in G. Dobson (1994, Ph.D. dissertation, Louisiana State University, Baton Rouge, LA) conjectured that every graph G with girth at least 2t+1 and minimum degree at least kÂt contains every tree T with k edges whose maximum degree does not excee

A theorem about a conjecture of H. Meyni

A theorem about a conjecture of H. Meyniel on kernel-perfect graphs

✍ Hortensia Galeana-Sánchez 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 391 KB

A digraph D is said to be an R-digraph (kernel-perfect graph) if all of its induced subdigraphs possesses a kernel (independent dominating subset). I show in this work that a digraph D, without directed triangles all of whose odd directed cycles C = (1, 2,..., 2n + 1, 1), possesses two short chords

On a Conjecture of Bannai and Ito: There

On a Conjecture of Bannai and Ito: There are Finitely Many Distance-regular Graphs with Degree 5, 6 or 7

✍ J.H. Koolen; V. Moulton 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 312 KB

Bannai and Ito conjectured in a 1987 paper that there are finitely many distance-regular graphs with fixed degree that is greater than two. In a series of papers they showed that their conjecture held for distance-regular graphs with degrees 3 or 4. In this paper we prove that the Bannai-Ito conject