Some results on overgraphs of a strongly regular graph (Q723422)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some results on overgraphs of a strongly regular graph |
scientific article |
Statements
Some results on overgraphs of a strongly regular graph (English)
0 references
31 July 2018
0 references
Let \(G=(V(G),E(G))\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). Let \(S\) be any (possibly empty) subset of the vertex set \(V(G)\) and define \(G_S\) to be the graph obtained from the graph \(G\) by adding a new vertex \(x\), which is adjacent exactly to the vertices from \(S\). Let \(i\) be a fixed vertex from the vertex set \(V(G)\) and let \(S_i\) denote the neighborhood of the vertex \(i\), defined as the set of all vertices of \(G\) which are adjacent to \(i\). We say that a regular graph \(G\) of order \(n\) and degree \(r \geq 1\) is strongly regular if there exist non-negative integers \(\tau\) and \(\theta\) such that \(|S_i \cap S_j| = \tau\) for any two adjacent vertices \(i\) and \(j\), and \(|S_i \cap S_j| = \theta\) for any two distinct non-adjacent vertices \(i\) and \(j\), understanding that \(G\) is not the complete graph \(K_n\). In this paper, the author proved the following interesting results: i) The author demonstrated that the characteristic polynomial of the corresponding graph \(G_S\) can be described by the parameters \(n, r, \tau\), and \(\theta\) of a connected strongly regular graph \(G\). In particular, the author established a characterization of all connected strongly regular graphs whose the corresponding graphs \(G_{S_i}\), \(G_{S_i^\bullet}\), \(G_{T_i}\), and \(G_{T_i^\bullet}\) have exactly two main eigenvalues, where \(S_i\) is the neighborhood of the vertex \(i\), \(S_i^\bullet=S_i\cup\{i\}\), \(T_i = V (G) \setminus S_i\) and \(T_i^\bullet= V (G) \setminus S_i^\bullet\). ii) The author demonstrated that the characteristic polynomial of the corresponding graphs \(G_{S,T}\) and \(G_{\dot{S},\dot{T}}\) can be described by the parameters \(n\), \(r\), \(\tau\), and \(\theta\) of a connected strongly regular graph \(G\), where \(G_{S,T}\) and \(G_{\dot{S},\dot{T}}\) are two graphs obtained from \(G\) by adding two new non-adjacent vertices \(x\), \(y\) and two new adjacent vertices \(x\), \(y\), respectively, so that \(x\) and \(y\) are adjacent in \(G\) exactly to the vertices from \(S\) and \(T = V (G)\setminus S\), respectively. In particular, for any regular graph \(G\), the authors give necessary and sufficient conditions under which the corresponding graphs \(G_{S,T}\) and \(G_{\dot{S},\dot{T}}\) have exactly two main eigenvalues.
0 references
strongly regular graph
0 references
eigenvalue
0 references
main eigenvalue
0 references
0 references