Characterizations of bipartite Steinhaus graphs
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\).
- Almost all steinhaus graphs have diameter 2
- Binomial Coefficients Modulo a Prime
- Bipartite Steinhaus graphs
- Generating strings for bipartite Steinhaus graphs
- Graphs without short odd cycles are nearly bipartite
- scientific article; zbMATH DE number 3829920 (Why is no real title available?)
- scientific article; zbMATH DE number 6004051 (Why is no real title available?)
- scientific article; zbMATH DE number 3655999 (Why is no real title available?)
- scientific article; zbMATH DE number 975321 (Why is no real title available?)
- scientific article; zbMATH DE number 3189338 (Why is no real title available?)
- Probability of diameter two for Steinhaus graphs
- Properties of Classes of Random Graphs
- Solution of Steinhaus's problem with plus and minus signs
- Steinhaus graphs
- Regular Steinhaus graphs of odd degree
- Generating strings for bipartite Steinhaus graphs
- Symmetric binary Steinhaus triangles and parity-regular Steinhaus graphs
- Planar Steinhaus graphs
- scientific article; zbMATH DE number 4137799 (Why is no real title available?)
- Pascal Triangle and Properties of Bipartite Steinhaus Graphs
- Parity-regular Steinhaus graphs
- Induced embeddings in Steinhaus graphs
- Balanced simplices
- scientific article; zbMATH DE number 4120200 (Why is no real title available?)
- scientific article; zbMATH DE number 5794154 (Why is no real title available?)
- scientific article; zbMATH DE number 2230278 (Why is no real title available?)
- Bipartite Steinhaus graphs
- Bipartite Steinhaus graphs
- Extremal cliques in Steinhaus graphs
This page was built for publication: Characterizations of bipartite Steinhaus graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1297427)