Cubic and quartic net-regular strongly regular signed graphs
Finite graphs equipped with an assignment of plus or minus one to each edge are called signed graphs. Accordingly, an edge is called positive or negative. Some standard graph-theory properties such as complete, connected, and regular, when applied to a signed graph, simply refer to properties of the underlying graph. Additionally, a vertex of a signed graph has a net degree, which is simply the number of positive edges incident with the vertex minus the number of negative edges incident with it. If all of the vertices have the same net degree, then the signed graph is said to be net-regular. For a signed graph, an evident matrix, analogous to the adjacency matrix of an ordinary graph, with entries that come from the set \(\{ -1, 0, 1 \}\), together with its eigenvalues and eigenvectors, plays a crucial role in cataloging and studying signed graphs. A signed graph is said to be strongly regular if its matrix satisfies a certain equation ((1) in the paper) that is analogous to the requirement on the adjacency matrix for an ordinary graph to be strongly regular.\N\NThis paper achieves the goal of classifying all signed graphs that are non-complete, connected, net-regular, strongly regular, and \(r\)-regular (in the ordinary graph sense), provided that \(r \le 4\). To accomplish this goal, it relies, in part, on previous results, such as a classification of the signed graphs whose eigenvalues are \(2\) and \(-2\), but the authors also painstakingly derive potential parameters for the desired signed graphs, construct those that can be constructed, and prove that the other possibilities do not exist. Section 5 compiles the results into one place. There are no such signed graphs when \(r = 1\). The only signed graph with \(r = 2\) is based on a 4-cycle. For \(r = 3\), they obtain the three signed graphs seen in Figure 1, and their ``negatives. For \(r = 4\), the situation is considerably more complicated. They obtain, together with their negatives, the last three signed graphs in Figure 2, and all four signed graphs in Figure 3. They also obtain an infinite family of signed graphs that are ``switch equivalent to the first signed graph (really a family of signed graphs) in Figure 2.\N\NIn an effort to help the reader avoid some of the confusion that initially troubled the reviewer, perhaps it will be useful to point out that the first signed graph (family of signed graphs) in Figure 2 is not even net-regular. Its inclusion in this figure seems out of place. It does not line up with the discussion that begins with Lemma 4.1. Another potential source of confusion is the phrase ``the coefficient of \(A_G\) in (1) at the start of the proof of Proposition 3.1. Here they mean \((a+b-2c)/2\), and not \((a+b)/2\), which is another coefficient of \(A_G\) in (1).
- A lexicographic product for signed graphs
- Constructing signed strongly regular graphs via star complement technique
- scientific article; zbMATH DE number 3482386 (Why is no real title available?)
- Integer symmetric matrices having all their eigenvalues in the interval \([ - 2,2]\)
- Integral regular net-balanced signed graphs with vertex degree at most four
- Linear ternary codes of strongly regular signed graphs
- Matrices in the theory of signed simple graphs
- Net regular signed trees
- Note on a zero net-regular signed graph
- On a class of strongly regular signed graphs
- On co-regular signed graphs
- On composition of signed graphs
- On signed graphs with just two distinct adjacency eigenvalues
- On strongly regular signed graphs
- Open problems in the spectral theory of signed graphs
- Regular graphs. A spectral approach
- Spectra of signed graphs with two eigenvalues
This page was built for publication: Cubic and quartic net-regular strongly regular signed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7021380)
