Characterizations of bipartite Steinhaus graphs
type: Item
instance of: scholarly article
title: Characterizations of bipartite Steinhaus graphs
zbMATH Open document ID: 0930.05080
DOI: 10.1016/S0012-365X(98)00282-9
author: V. Pereyra
published in: Discrete Mathematics
publication date: 2000-01-18T00:00:00Z
review text: For a binary sequence \(T=a_{0,0} a_{0,1}\dots a_{0,n}\) with \(a_{0,0}=0\) the Steinhaus graph generated by \(T\) is defined by the adjacency matrix \(A=[a_{i,j}]\) with \[ a_{i,j}=\begin{cases} 0 &\text{if \(0\leq i=j\leq n-1,\)}\\ (a_{i-1,j-1}+a_{i-1,j})\bmod 2 &\text{if \(0<i<j\leq n-1,\)}\\ a_{j,i} &\text{otherwise.}\end{cases} \] Let min\(\text{Adj} (0)\) be the vertex with the smallest number that is adjacent to vertex \(0\), and let \(\text{Adj} ^+(v)\) be the set of all vertices with numbers exceeding \(v\) that are adjacent to \(v\). It is easily shown that a Steinhaus graph is determined uniquely if \(v=\text{minAdj}(0)\) and \(\text{Adj} ^+(v)\) are given. The authors split the bipartite Steinhaus graphs into four classes and characterize each of the classes in terms of \(v\) and \(\text{Adj} ^+(v)\). They also compute the number \(b(n)\) of bipartite Steinhaus graphs with \(n\) vertices in each class and provide a tight bound on \(b(n)\) for \(n\geq 4\) of the form \(\lceil{1\over 8}(17n-22)\rceil\leq b(n)\leq \lfloor{1\over 2}(5n-7)\rfloor\).
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1321788
zbMATH Keywords: Steinhaus graph
zbMATH Keywords: recursive sequence
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
cites work: Almost all steinhaus graphs have diameter 2
cites work: Probability of diameter two for Steinhaus graphs
cites work: Properties of Classes of Random Graphs
cites work: Q3113195
cites work: Q5283983
cites work: Q3037444
cites work: Q3855229
cites work: Bipartite Steinhaus graphs
cites work: Generating strings for bipartite Steinhaus graphs
cites work: Binomial Coefficients Modulo a Prime
cites work: Graphs without short odd cycles are nearly bipartite
cites work: Solution of Steinhaus's problem with plus and minus signs
cites work: Steinhaus graphs
cites work: Q5725656
Wikidata QID: Q126572867
description: scientific article; zbMATH DE number 1321788