Home Page Image
 

February 6-10, 2012
Ghent (Belgium)

Organizers:

Bart De Bruyn,
Tom De Medts,
Jef Thas,
Koen Thas,
Hendrik Van Maldeghem

  


Akihiro Munemasa

Graphs with complete multipartite \(\mu\)-graphs

(joint work with A. Jurišić and Y. Tagami)

A graph \(\Gamma\) is said to be locally \(\Delta\) if the neighborhood of every vertex of \(\Gamma\) is isomorphic to the graph \(\Delta\). A \(\mu\)-graph of a graph is the subgraph induced on the set of common neighbors of two vertices at distance \(2\). If every \(\mu\)-graph of \(\Delta\) is isomorphic to a fixed graph \(M\), then every \(\mu\)-graph of a locally \(\Delta\) graph \(\Gamma\) is locally \(M\). In short:
local graph of \(\mu\)-graph \(\cong\) \(\mu\)-graph of local graph.
The same idea can be used for classifying graphs with given \(\mu\)-graph. In a graph with prescribed \(\mu\)-graph, \(\mu\)-graphs of local graphs are determined automatically. The situation is particularly simple if we consider \(K_{t\times n}\) as \(\mu\)-graphs, where \(K_{t\times n}\) denotes the complete multipartite graph with \(t\) parts, each of which consists of an \(n\)-coclique. Its local graph is \(K_{(t-1)\times n}\), so we have:
If every \(\mu\)-graph of a graph \(\Gamma\) is isomorphic to \(K_{t\times n}\), then every local graph of \(\Gamma\) has \(\mu\)-graphs isomorphic to \(K_{(t-1)\times n}\).
That is, graphs with complete multipartite \(\mu\)-graphs are closed under the operation of taking local graphs.

Examples include the Johnson graph \(J(8,4)\), the halved \(8\)-cube, the known generalized quadrangle of order \((4, 2)\), an antipodal distance-regular graph constructed by T. Meixner and the Patterson graph.

We investigate this class of graphs with an additional assumption that the intersection number \(\alpha\) exists, which means that for a triple \((x, y, z)\) of vertices in \(\Gamma\), such that \(x\) and \(y\) are adjacent and \(z\) is at distance \(2\) from \(x\) and \(y\), the number \(\alpha(x, y, z)\) of common neighbors of \(x\), \(y\) and \(z\) does not depend on the choice of a triple.

We show that if \(\Gamma\) is a graph whose \(\mu\)-graphs are all isomorphic to \(K_{t\times n}\) and whose intersection number \(\alpha\) exists, then \(\alpha = t\), as conjectured by Jurišić and Koolen (2007), provided \(\alpha \geq 2\). We also prove that \(t\leq4\), and that equality holds only when \(\Gamma\) is the unique distance-regular graph \(3.O_7(3)\).