Distance regularity of compositions of graphs.
type: Item
instance of: scholarly article
title: Distance regularity of compositions of graphs.
zbMATH Open document ID: 1063.05137
DOI: 10.1016/S0893-9659(04)90072-9
author: Dragan Stevanović
published in: Applied Mathematics Letters
publication date: 2005-02-25T00:00:00Z
review text: The strong sum of graphs \(G_1\) and \(G_2\), \( G_1 \oplus G_2 \), is the graph whose vertex set is the Cartesian product \(V(G_1) \times V(G_2)\), and \((u_1,v_1)\) is adjacent to \((u_2,v_2)\) if \(u_1\) is adjacent to \(u_2\) and \(v_1\) is adjacent to \(v_2\) or if \(u_1\) is adjacent to \(u_2\) and \(v_1 = v_2\). The strong product \(G_1 \otimes G_2\) has the same vertex set and \((u_1,v_1)\) is adjacent to \((u_2,v_2)\) if \(u_1\) is adjacent to \(u_2\) and \(v_1\) is adjacent to \(v_2\) or if \(u_1\) is adjacent to \(u_2\) and \(v_1 = v_2\) or if \(u_1 = u_2\) and \(v_1\) is adjacent to \(v_2\). The main question of the paper is the one of determining the circumstances under which the strong sum or the strong product of distance regular graphs is distance regular. The author obtains a complete classification of the above situation(s). For the case of the strong product, the main theorem asserts that the strong product \(G_1 \otimes G_2\) of two connected distance regular graphs is distance regular if and only if both \(G_1\) and \(G_2\) are complete (of possibly different sizes). The case of the strong sum splits into two cases depending on the size of the first graph: if \(G_1\) has at least three vertices, and both \(G_1\) and \(G_2\) are connected and distance regular, then \(G_1 \oplus G_2\) is distance regular if and only if \(G_1\) is isomorphic to the complete multipartite graph with \(t\) parts of size \(m\) (for some \(t\) and \(m\)) and \(G_2\) is a complete graph; in the case when \(G_1=K_2\) and \(G_2\) is connected and distance regular, \(G_1 \oplus G_2\) is distance regular if and only if \(G_2\) satisfies two additional conditions on its distance parameters (stated in the form of equations). The key to the classification is a careful examination of the distance properties of the strong sum and strong product of connected graphs.
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 2138590
zbMATH Keywords: distance regular graphs
zbMATH Keywords: strong sum of graphs
zbMATH Keywords: strong product of graphs
reviewed by: Robert Jajcay
MaRDI profile type: Publication
cites work: Q3992965
cites work: Q3941433
cites work: Q5648382
cites work: Q4327350
cites work: Q3697044
cites work: Distance regularity in direct-product graphs
cites work: When is NEPS of graphs connected?
cites work: Characterization of H(n,q) by the parameters
cites work: The Uniqueness of the $\mathrm{L}_2$ Association Scheme
cites work: Diameter of the NEPS of bipartite graphs
full work available at URL: s0893-9659(04)90072-9
OpenAlex ID: W1980723504
description: scientific article; zbMATH DE number 2138590